算法入门（七）：动态规划 - 基础题目

动态规划

动态规划/DP/Dynamic Programming：面对某一有很多重叠子问题的情况，采用动态规划，即每一个状态一定是由上一个状态推导出来的。

数学计算类

Leetcode 118 - 杨辉三角

来试一试HOT100里的简单题。

首先尝试理解这个三角形，第一行、第二行全是1，第三行的非首非尾的元素是通过递推式得来的。
于是每一行可以设置为path并初始化为1，这是外循环；path的第i个 = 上一行的res的第i个和i-1个，这是内循环。

classSolution{public:vector<vector<int>>generate(intnumRows){intn=numRows;vector<vector<int>>res(n);vector<int>path;for(inti=0;i<n;i++){path.resize(i+1,1);for(intj=1;j<i;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(n==0)return0;if(n==1)return1;returnfib(n-1)+fib(n-2);}};

当n=5的时候，求fib(5)，需要fib(4)和fib(3)，以此类推，文字不便理解，用图表示：

一眼便知，时间复杂度为O(2^n) 。

接下来尝试动态规划，新建一个dp数组，如果是dp(n,0)就是n个元素，也就是从0到n-1。所以需要n+1个元素，即 vector dp(n+1, 0) 。

classSolution{public:intfib(intn){if(n<=1)returnn;vector<int>dp(n+1,0);dp[0]=0;dp[1]=1;for(inti=2;i<=n;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){vector<int>dp(n+1,0);if(n<=2){returnn;}dp[1]=1;dp[2]=2;for(inti=3;i<=n;i++){dp[i]=dp[i-1]+dp[i-2];}returndp[n];}};

Leetcode 746 - 使用最小花费爬楼梯

Leetcode 746 - 使用最小花费爬楼梯
这道题相比于Leetcode 70更复杂，传入了cost数组。dp不是由某两个状态相加而来，而是由两个状态比较，取最小得来。

classSolution{public:intminCostClimbingStairs(vector<int>&cost){intn=cost.size();vector<int>dp(n+1);dp[0]=0;dp[1]=0;for(inti=2;i<=n;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,vector<int>&costs){if(n==0)return0;vector<int>dp(n+1);dp[0]=0;if(n>=1)dp[1]=dp[0]+costs[0]+1;if(n>=2)dp[2]=min(dp[0]+costs[1]+4,dp[1]+costs[1]+1);if(n>=3)dp[3]=min({dp[0]+costs[2]+9,dp[1]+costs[2]+4,dp[2]+costs[2]+1});for(inti=4;i<=n;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];}};