C++动态规划 DP（1）

C动态规划 DP动态规划把大问题拆成小问题把小问题算出来用dp数组存起来大问题用小问题解决递推不用重复算。1、斐波那契数列题目大意1 1 2 3 5 8 13 21 34 …公式dp[n]dp[n-1]dp[n-2]#includebits/stdc.h using namespace std; int main(){ int n; cinn;//找第n位元素是什么从1开始 int dp[100]; //设初始条件 dp[1]1; dp[2]1; //递推 for(int i3;in;i){ dp[i]dp[i-1]dp[i-2]; } coutdp[n];//第n位元素的数字 return 0; }2、爬楼梯题目大意一次爬1阶或者2阶爬到n阶有几种方法1 2 3 5 8 13 21 34…公式dp[n]dp[n-1]dp[n-2]#includebits/stdc.h using namespace std; int main(){ int n; cinn; int dp[105]; dp[1]1; dp[2]2; for(int i3;in;i){ dp[i]dp[i-1]dp[i-2]; } coutdp[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])#includebits/stdc.h using namespace std; int main(){ int n; cinn; int a[105],dp[105]; for(int i0;in;i){ cina[i]; } dp[1]a[1]; dp[2]max(a[1],a[2]); for(int i3;in;i){ dp[i]max(dp[i-1],dp[i-2]a[i]);//在不偷第i间与偷第i间中选一个最大值 } coutdp[n]; return 0; }