算法入门七动态规划 - 基础题目动态规划数学计算类Leetcode 118 - 杨辉三角Leetcode 509 - 斐波那契数爬楼梯Leetcode 70 - 爬楼梯Leetcode 746 - 使用最小花费爬楼梯Leetcode 3693 - 爬楼梯 Ⅱ动态规划动态规划/DP/Dynamic Programming面对某一有很多重叠子问题的情况采用动态规划即每一个状态一定是由上一个状态推导出来的。数学计算类Leetcode 118 - 杨辉三角来试一试HOT100里的简单题。首先尝试理解这个三角形第一行、第二行全是1第三行的非首非尾的元素是通过递推式得来的。于是每一行可以设置为path并初始化为1这是外循环path的第i个 上一行的res的第i个和i-1个这是内循环。classSolution{public:vectorvectorintgenerate(intnumRows){intnnumRows;vectorvectorintres(n);vectorintpath;for(inti0;in;i){path.resize(i1,1);for(intj1;ji;j){path[j]res[i-1][j-1]res[i-1][j];}res[i]path;}returnres;}};可以看到动态规划所说的“每一个状态是由上一个状态推导出来的”便在path[j] res[i - 1][j - 1] res[i - 1][j];体现出来。Leetcode 509 - 斐波那契数Leetcode 509 - 斐波那契数首先理解递归写法classSolution{public:intfib(intn){if(n0)return0;if(n1)return1;returnfib(n-1)fib(n-2);}};当n5的时候求fib(5)需要fib(4)和fib(3)以此类推文字不便理解用图表示一眼便知时间复杂度为O(2^n) 。接下来尝试动态规划新建一个dp数组如果是dp(n,0)就是n个元素也就是从0到n-1。所以需要n1个元素即 vector dp(n1, 0) 。classSolution{public:intfib(intn){if(n1)returnn;vectorintdp(n1,0);dp[0]0;dp[1]1;for(inti2;in;i){dp[i]dp[i-1]dp[i-2];}returndp[n];}};按照这个递推公式dp[i] dp[i - 1] dp[i - 2]我们来推导一下当N为10的时候dp数组应该是0 1 1 2 3 5 8 13 21 34 55。爬楼梯Leetcode 70 - 爬楼梯Leetcode 70 - 爬楼梯模仿 Leetcode 509注意边界条件就可以。classSolution{public:intclimbStairs(intn){vectorintdp(n1,0);if(n2){returnn;}dp[1]1;dp[2]2;for(inti3;in;i){dp[i]dp[i-1]dp[i-2];}returndp[n];}};Leetcode 746 - 使用最小花费爬楼梯Leetcode 746 - 使用最小花费爬楼梯这道题相比于Leetcode 70更复杂传入了cost数组。dp不是由某两个状态相加而来而是由两个状态比较取最小得来。classSolution{public:intminCostClimbingStairs(vectorintcost){intncost.size();vectorintdp(n1);dp[0]0;dp[1]0;for(inti2;in;i){dp[i]min(dp[i-1]cost[i-1],dp[i-2]cost[i-2]);}returndp[n];}};Leetcode 3693 - 爬楼梯 ⅡLeetcode 3693 - 爬楼梯 Ⅱ非常朴实的写法完全照搬题意注意dp和cost的下标的含义。classSolution{public:intclimbStairs(intn,vectorintcosts){if(n0)return0;vectorintdp(n1);dp[0]0;if(n1)dp[1]dp[0]costs[0]1;if(n2)dp[2]min(dp[0]costs[1]4,dp[1]costs[1]1);if(n3)dp[3]min({dp[0]costs[2]9,dp[1]costs[2]4,dp[2]costs[2]1});for(inti4;in;i){dp[i]min({dp[i-3]costs[i-1]9,dp[i-2]costs[i-1]4,dp[i-1]costs[i-1]1});}returndp[n];}};