免费做爰网站余姚网站seo运营
Day38 动态规划
又开始了新的章节，有了点难度的感觉。。
动态规划五部曲：
确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组
这些以后慢慢参透
LeetCode 509.斐波纳契数
最简单的动态规划，甚至不需要动态规划就可以解决的问题。初始状态、递推公式都已经有了，这道题就很简单了。
class Solution {
public:int fib(int n) {if(n<=1) return n;vector<int> 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];}
};
LeetCode 76.爬楼梯
爬楼梯的关键是递推公式的推导，如果能推导出来每一层是由前两层走上来的，那么这道题几乎就是一个变种的斐波纳契数列了。
class Solution {
public:int climbStairs(int n) {if(n<=1) return n;vector<int> 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];}
};
LeetCode 746. 使用最小花费爬楼梯
dp数组的含义：到达i位置的花费为dp[i]
递推公式：dp[i-1]+cost[i-1]和dp[i-2]+cost[i-2]的最小值
初始化：dp[0]=dp[1]=0
遍历顺序：正序
class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {vector<int> dp(cost.size()+1);dp[0]=0;dp[1]=0;for(int i=2;i<=cost.size();i++)dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);return dp[cost.size()];}
};
动态规划继续加油！