C++动态规划 DP

动态规划把大问题拆成小问题，把小问题算出来用dp数组存起来，大问题用小问题解决，递推，不用重复算。

1、斐波那契数列

题目大意：1 1 2 3 5 8 13 21 34 …

公式：dp[n]=dp[n-1]+dp[n-2]

#include<bits/stdc++.h> using namespace std; int main(){ int n; cin>>n;//找第n位元素是什么，从1开始 int dp[100]; //设初始条件 dp[1]=1; dp[2]=1; //递推 for(int i=3;i<=n;i++){ dp[i]=dp[i-1]+dp[i-2]; } cout<<dp[n];//第n位元素的数字 return 0; }

2、爬楼梯

题目大意：一次爬1阶，或者2阶，爬到n阶有几种方法

1 2 3 5 8 13 21 34…

公式：dp[n]=dp[n-1]+dp[n-2]

#include<bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; int dp[105]; dp[1]=1; dp[2]=2; for(int i=3;i<=n;i++){ dp[i]=dp[i-1]+dp[i-2]; } cout<<dp[n]; return 0; }

3、打家劫舍

题目大意：一排房子，每间房子有固定钱财。不能偷相邻两间房子，求最多能偷多少钱。

定义dp, dp[i]：前i间房子，能偷到的最大总钱数

只有1间时，只能偷它，dp[1]=a[1]

有两间时：选钱多的那一间，dp[2]=max(a[1],a[2])

到第i间只有两种选择

1、不偷第i间：最大值=dp[i-1]

2、偷第i间：就不能偷i-1间，只能用dp[i-2]+a[i]；

公式：dp[i]=max(dp[i-1],dp[i-2]+a[i])

#include<bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; int a[105],dp[105]; for(int i=0;i<n;i++){ cin>>a[i]; } dp[1]=a[1]; dp[2]=max(a[1],a[2]); for(int i=3;i<=n;i++){ dp[i]=max(dp[i-1],dp[i-2]+a[i]);//在不偷第i间与偷第i间中选一个最大值 } cout<<dp[n]; return 0; }