本文主要是介绍代码随想录训练营Day29:动态规划1，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。
1.动态规划的解题步骤
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
找问题的最好方式就是把dp数组打印出来，看看究竟是不是按照自己思路推导的！
做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。
2.509斐波那契数
在这里就不讨论递归和for循环的方式，而是讨论使用动态规划的方式进行推导
1.确定dp[i]的含义：F(i)的值。
2.确定递推公式：dp[i] = dp[i-1] +dp[i-2];//右斐波那契数列的定义可知
3.数组初始化:vector<int> dp(n+1);dp[0]=0;dp[1] = 1;//在这里初始化的长度为n+1.
4.遍历顺序，从小到大遍历
下面的第一种方式是dp数组的变式，因为我们始终只使用了三个数，即dp[i],dp[i-1],dp[i-2]所以如果想要节约内存空间，可以使用三个int类型来进行代替并进行更新即可。
class Solution {
public:int fib(int n) {//这是只有两个数来代替dp数组的/*if(n == 0|| n == 1) return n;int sum0 = 0; //dp数组的初始化int sum1 = 1;int result = 0;for(int i = 2;i <= n;i++){result = sum0+sum1;sum0 = sum1;sum1 = result;}return result;*/if(n == 0|| n == 1) return n;vector<int> dp(n+1,0);//初始化dp[1] = 1;for(int i=2;i<n+1;i++){dp[i] = dp[i-1]+dp[i-2];}return dp[n];}
};3.70爬楼梯
和前面的斐波那契数有相同的思路，在这个地方我们需要反向思考，要达到n处，那么我上一步的位置是：n-1或n-2的位置，所以dp[n] = dp[n-1]+dp[n-2];总体来说和上面那个问题差不多。
class Solution {
public:int climbStairs(int n) {/*if(n == 1) return 1;int sum0 = 1; //dp数组的初始化int sum1 = 1;int result;for(int i = 2;i <= n;i++){result = sum0+sum1;sum0 = sum1;sum1 = result;}return result;*/vector<int> dp(n+1,1);//初始化的时候，爬到1只有一种方法for(int i = 2;i<n+1;i++){dp[i] = dp[i-1]+dp[i-2];//i-1代表爬到i-1的位置再爬一步，i-2代表爬到i-2再爬两步}return dp[n];}
};4.764使用最小花费爬楼梯
- 确定dp数组（dp table）以及下标的含义：dp[i]代表走到i处的最小花费
- 确定递推公式：dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);//代表的是走到i处上一步两种情况下的最小花费。扩展：在这个地方如果一次走的不是1步或者两步，那么此时就需要使用for循环来求这个的最小花费了。
- dp数组如何初始化：vector<int> dp(n+1,0);//dp[0] = 0,dp[1] = 0;初始化，由于一开始的位置可以在0,也可以在1.
- 确定遍历顺序：从小到大进行遍历。
class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {/*int len = cost.size();if(len <= 1) return 0;//dp数组，到达i处的最小花费int dp0 = 0,dp1 = 0;int result = 0;for(int i = 2;i <= len;i++){result = min(dp0+cost[i-2],dp1+cost[i-1]);dp0 = dp1 ;dp1 = result;}return result;*///dp[i]爬到i处的最小花费int n = cost.size();vector<int> dp(n+1,0);//dp[0] = 0,dp[1] = 0;初始化for(int i = 2;i<=n;i++){dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);//代表从i-1,i-2开始分别走到这需要的最小花费}return dp[n];}
};这篇关于代码随想录训练营Day29:动态规划1的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
