菜鸡刷算法的一天，每天分享两题算法，大家有这个想法的，可以给我个关注，然后一起坚持每天的算法之旅。希望我们共同进步，一起加油。 动规算法采用了 代码随想录 的动规五部
LC
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 1：
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。
示例 2：
输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。
解题思路：使用动规五部曲。到达当前楼梯 i 有两种方法，一种由 i - 1来，一种由 i - 2来。
代码：
var minCostClimbingStairs = function(cost) {
let dp = [cost[0], cost[1]];
for(let i = 2; i < cost.length; i++) {
dp[i] = Math.min(dp[i - 1] + cost[i], dp[i - 2] + cost[i]); //将当前值与上一个值和当前值与上二个值进行对比，选取最小的。
}
return Math.min(dp[cost.length -1], dp[cost.length - 2]) //返回倒一和倒二中最小的值
};
LC
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7
输出：28
示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
示例 3：
输入：m = 7, n = 3
输出：28
示例 4：
输入：m = 3, n = 3
输出：6
解题思路：动规五部曲。递归公式：每一个 （i，j）位置都是从（i-1，j）或者（i，j-1）而来的
代码：
var uniquePaths = function(m, n) {
let dp = Array(m).fill().map(item => Array(n)); //创建二维数组
for(let i = 0; i < m; i++) {
dp[i][0] = 1; //将每行第一个的路径值都设为 1
}
for(let i = 0; i < n; i++) {
dp[0][i] = 1; //将每列第一个的路径值都设为 1
}
for (let i = 1; i < m; ++i) {
for (let j = 1; j < n; ++j) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] //每个dp[i][j] 都从 dp[i-1][j] 或 dp[i][j - 1]来的
}
}
return dp[m - 1][n - 1]
};