5月3日ccpc省賽還有13天左右，決定先刷動態(tài)規(guī)劃的題，之后有時間就刷dfs和bfs。

今天刷了4題動態(tài)規(guī)劃，都是比較簡單的。

DP1?斐波那契數(shù)列

#include<bits/stdc++.h>

using namespace std;

int main(int argc, char const *argv[]) {

? int f[41]={0},n=0;

? f[1]=1,f[2]=1;

? cin>>n;

? if(n==1||n==2)

? {

? ? cout<<1;

? ? return 0;

? }

? else

? {

? ? for (int i = 3; i <= n; i++)

? ? {

? ? ? f[i]=f[i-1]+f[i-2];

? ? }

? ? cout<<f[n];

? }

? return 0;

}

基礎(chǔ)中的基礎(chǔ)。

DP2?跳臺階

一只青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個 n 級的臺階總共有多少種跳法（先后次序不同算不同的結(jié)果）。

數(shù)據(jù)范圍：$0\le n\le 40$

要求：時間復(fù)雜度：O(n)，空間復(fù)雜度：?O(1)

code：

#include<bits/stdc++.h>

using namespace std;

int main(int argc, char const *argv[]) {

? int f[41]={1},n=0;

? f[1]=1,f[2]=2;

? cin>>n;

? if(n==1)

? {

? ? cout<<1;

? ? return 0;

? }

? else if(n==2)

? {

? ? cout<<2;

? ? return 0;

? }

? else

? {

? ? for (int i = 3; i <= n; i++)

? ? {

? ? ? f[i]=f[i-1]+f[i-2];

? ? }

? ? cout<<f[n];

? }

? return 0;

}

這讓我想起少年班的那個神棍。

和斐波那契數(shù)列一樣只不過發(fā)f（2）= 2

DP3?跳臺階擴(kuò)展問題

一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階(n為正整數(shù))總共有多少種跳法。

數(shù)據(jù)范圍：$1\le n\le 20$
進(jìn)階：空間復(fù)雜度?O(1)?， 時間復(fù)雜度?O(1)

code：

#include<bits/stdc++.h>

using namespace std;

//an=a?*q??1

int main(int argc, char const *argv[]) {

? int n=0;

? cin>>n;

? cout<<pow(2,n-1);

? return 0;

}

考慮????f(n)=f(n-1)+f(n-2)+....+f(1)

?????????? ?且f(n-1)= f(n-2)+.....+f(1)

所以f（n）= 2f（n-1）

所以可以用動態(tài)規(guī)劃來解

但題目要求時間復(fù)雜度為O(1)

所以仔細(xì)思考后 即可用等差公式 an=a?*q??1 其中 q=2，a?=1

所以結(jié)果可為?pow(2,n-1)

我想起那個p=np？的難題

DP4?最小花費(fèi)爬樓梯

給定一個整數(shù)數(shù)組?$cost$?，其中?$cost[i]$?是從樓梯第$i$個臺階向上爬需要支付的費(fèi)用，下標(biāo)從0開始。一旦你支付此費(fèi)用，即可選擇向上爬一個或者兩個臺階。

你可以選擇從下標(biāo)為 0 或下標(biāo)為 1 的臺階開始爬樓梯。

請你計算并返回達(dá)到樓梯頂部的最低花費(fèi)。

數(shù)據(jù)范圍：數(shù)組長度滿足?$1\le n\le 10$?，數(shù)組中的值滿足?$1\le cost\le 10$

code：

#include<bits/stdc++.h>

using namespace std;

int main(int argc, char const *argv[]) {

? int n;

? int cost[100000]={0};

? int pay[100000]={0};

? cin>>n;

? for (int i = 0; i < n; i++) {

? ? cin>>cost[i];

? }

? if(n==1||n==0)

? {

? ? cout<<0;

? }

? pay[1]=cost[1],pay[0]=cost[0];

? for (int i = 2; i <= n; i++) {

? ? //if(pay[i-1]!=pay[i-2])

? ? ? pay[i]=min(pay[i-2],pay[i-1])+cost[i];

? ? // else

? ? //? ?pay[i]=

? }

? // for (int i = 0; i <= n; i++) {

? //? ?cout<<i<<":"<<pay[i]<<endl;

? // }

? cout<<pay[n]-cost[n];

? return 0;

}

下次寫這種題目主要每個函數(shù)，數(shù)組，變量的定義都要十分清楚，最好寫紙上或?qū)懮蟼渥ⅲ?/p>

這題的思路主要是 當(dāng)?shù)絃（n），?n》1時考慮最后一步還是兩步，這用min（）來區(qū)別。

最后到n層樓的代價，則是 從樓底到跨出n層樓所需的代價減去只跨出n層樓的代價即可。