动态规划理论基础
解题模版：动规五部曲
- 确定dp数组下标的含义
- 确定递推公式
- 确定初始值
- 确定遍历顺序
- 举例推到
最好将每一步打印下来。
斐波那契数
var fib = function(n) {
let dp=[]
dp[0]=0
dp[1]=1
for(let i=2;i<=n;i++){
dp[i]=dp[i-1]+dp[i-2]
}
return dp[n]
};
爬楼梯
var climbStairs = function(n) {
let dp=[]
dp[0]=0
dp[1]=1;
dp[2]=2;
for(let i=3;i<=n;i++){
dp[i]=dp[i-1]+dp[i-2]
}
return dp[n]
};
使用最小花费爬楼梯
力扣题目链接
自己的分析：
- dp 数组：到达第i梯的最低花费
- 状态转移方程： dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
- 初始状态： dp[0] dp[1] 均为0，不需要花销
- 遍历顺序：顺序
bingo！
var minCostClimbingStairs = function(cost) {
let dp = [];
// dp[i] 到达第i梯的最低花费
dp[0] = 0;
dp[1] = 0;
for (let i = 2; i <= cost.length; i++) {
dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[dp.length - 1];
};
