《代码随想录》刷题打卡day28：动态规划part01

文章目录1. 动态规划Dynamic Programming理论1什么是动态规划2动态规划解题步骤2.题目打卡【509.斐波那契数】【70.爬楼梯】【746.使用最小花费爬楼梯】1. 动态规划Dynamic Programming理论1什么是动态规划如果某一问题有很多重叠子问题使用动态规划是最有效的。所以动态规划中每一个状态一定是由上一个状态推导出来的这一点就区分于贪心贪心没有状态推导而是从局部直接选最优的。**例如**有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。动态规划中dp[j]是由dp[j-weight[i]]推导出来的然后取max(dp[j], dp[j - weight[i]] value[i])。但如果是贪心呢每次拿物品选一个最大的或者最小的就完事了和上一个状态没有关系。所以贪心解决不了动态规划的问题。2动态规划解题步骤确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组做动规的题目写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍心中有数确定最后推出的是想要的结果。然后再写代码如果代码没通过就打印dp数组看看是不是和自己预先推导的哪里不一样。如果打印出来和自己预先模拟推导是一样的那么就是自己的递归公式、初始化或者遍历顺序有问题了。如果和自己预先模拟推导的不一样那么就是代码实现细节有问题。2.题目打卡【509.斐波那契数】动规五部曲这里我们要用一个一维dp数组来保存递归的结果确定dp数组以及下标的含义dp[i]的定义为第i个数的斐波那契数值是dp[i]确定递推公式为什么这是一道非常简单的入门题目呢因为题目已经把递推公式直接给我们了状态转移方程 dp[i] dp[i - 1] dp[i - 2];dp数组如何初始化题目中把如何初始化也直接给我们了如下dp[0] 0; dp[1] 1;确定遍历顺序从递归公式dp[i] dp[i - 1] dp[i - 2];中可以看出dp[i]是依赖 dp[i - 1] 和 dp[i - 2]那么遍历的顺序一定是从前到后遍历的举例推导dp数组按照这个递推公式dp[i] dp[i - 1] dp[i - 2]我们来推导一下当N为10的时候dp数组应该是如下的数列0 1 1 2 3 5 8 13 21 34 55如果代码写出来发现结果不对就把dp数组打印出来看看和我们推导的数列是不是一致的。class Solution { public: int fib(int n) { if(n 1) return n; vectorint dp(n 1); dp[0] 0; dp[1] 1; for(int i 2; i n; i){ dp[i] dp[i-1] dp[i-2]; } return dp[n]; } };【70.爬楼梯】class Solution { // dp[i]表示到当前楼层所有的方法数dp[i] dp[i-1] do[i-2] public: int climbStairs(int n) { if(n 2) return n; vectorint dp(n 1); dp[1] 1; dp[2] 2; for(int i 3; i n; i){ dp[i] dp[i-1] dp[i-2]; } return dp[n]; } };【746.使用最小花费爬楼梯】class Solution { //dp[i]表示上到i台阶所需要的最低花费 public: int minCostClimbingStairs(vectorint cost) { int height cost.size(); vectorint dp(height1); dp[0] 0; dp[1] 0; for(int i 2; i height; i){ dp[i] min(dp[i-1] cost[i-1], dp[i-2] cost[i-2]); } return dp[height]; } };