C++ 动态规划
动规五部曲:
这⾥我们要⽤⼀个⼀维dp数组来保存递归的结果
- 确定dp数组以及下标的含义
dp[i]的定义为:第i个数的斐波那契数值是dp[i] - 确定递推公式
状态转移⽅程 dp[i] = dp[i - 1] + dp[i - 2]; - dp数组如何初始化
题⽬中把如何初始化也直接给我们了,如下: - 确定遍历顺序
从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出, dp[i]是依赖 dp[i - 1] 和 dp[i - 2],那么遍历的顺序
⼀定是从前到后遍历的 - 举例推导dp数组
如果代码写出来,发现结果不对,就把dp数组打印出来看看和我们推导的数列是不是⼀致的。
以上我们⽤动规的⽅法分析完了, C++代码如下#include<iostream> #include<vector> using namespace std; int main() { int month; while(cin>>month) { if(month==1||month==2) { cout<<1<<endl; } vector<int> dp(month+1,0); dp[1]=1; dp[2]=1; for(int i=3;i<=month;i++) { dp[i]=dp[i-1]+dp[i-2]; } cout<<dp[month]<<endl; } }