4 746 运用最小花费爬楼梯

力扣标题链接

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的膂力花费值cost[i]（下标从 0 开端）。

每逢你爬上一个阶梯你都要花费对应的膂力值，一旦支付了相应的膂力值，你就能够挑选向上爬一个阶梯或许爬两个阶梯。

请你找出抵达楼层顶部的最低花费。在开端时，你能够挑选从下标为 0 或 1 的元素作为初始阶梯。

示例1：

输入：cost = [10, 15, 20] 输出：15 解说：最低花费是从 cost[1] 开端，然后走两步即可到阶梯顶，总共花费 15 。 示例 2：

输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 输出：6 解说：最低花费办法是从 cost[0] 开端，逐一通过那些 1 ，跳过 cost[3] ，总共花费 6 。

提示：

  • cost 的长度规模是 [2, 1000]。
  • cost[i] 将会是一个整型数据，规模为 [0, 999]

4.1 思路

这道标题能够说是之前写的动态规划：爬楼梯的花费版别。

留意标题描绘：每逢你爬上一个阶梯你都要花费对应的膂力值，一旦支付了相应的膂力值，你就能够挑选向上爬一个阶梯或许爬两个阶梯

所以示例1中只花费一个15 就能够到阶梯顶，最终一步能够了解为 不必花费。

运用动态规划 五部曲：

  1. 确认dp数组以及下标的意义

动态规划，运用一维数组dp[i]

dp[i]的界说：抵达第i个台阶所花费的最少膂力为dp[i] 。（留意这里认为是第一步必定是要花费）

关于dp数组的界说，大家必定要清晰！

  1. 确认递推公式

有两个途径得到dp[i]，一个是dp[i-1] 一个是dp[i-2] 。

那么究竟是选dp[i-1]仍是dp[i-2]呢？

必定是选最小的，所以dp[i] = min(dp[i – 1], dp[i – 2]) + cost[i];（表明：当时到i花费的总膂力 = 到i-1或i-2时花费的总膂力 + i处花费的膂力）

留意这里为什么是加cost[i]，而不是cost[i-1],cost[i-2]之类的，由于标题中说了：每逢你爬上一个阶梯你都要花费对应的膂力值

  1. dp数组怎么初始化

根据dp数组的界说，dp数组初始化其实是比较难的，由于不可能初始化为第i台阶所花费的最少膂力。

那么看一下递归公式，dp[i]由dp[i-1]，dp[i-2]推出，既然初始化所有的dp[i]是不可能的，那么只初始化dp[0]和dp[1]就够了，其他的最终都是dp[0]dp[1]推出。

dp[0] = cost[0]; dp[1] = cost[1];

  1. 确认遍历次序

由于是模仿台阶，而且dp[i]又dp[i-1]dp[i-2]推出，所以是从前到后遍历cost数组就能够了。

可是稍稍有点难度的动态规划，其遍历次序并不简单确认下来。

例如：01背包，都知道两个for循环，一个for遍历物品嵌套一个for遍历背包容量，那么为什么不是一个for遍历背包容量嵌套一个for遍历物品呢？ 以及在运用一维dp数组的时分遍历背包容量为什么要倒序呢？

  1. 举例推导dp数组

拿示例2：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ，来模仿一下dp数组的状态改变，如下：

动态规划Ⅱ（使用最小花费爬楼梯，不同路径）

假如大家代码写出来有问题，就把dp数组打印出来，看看和如上推导的是不是一样的。

4.2 代码

C++代码如下：

// 版别一
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(cost.size());
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < cost.size(); i++) {
            dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
        }
        // 留意最终一步能够了解为不必花费，所以取倒数第一步，第二步的最少值
        return min(dp[cost.size() - 1], dp[cost.size() - 2]);
    }
};
  • 时刻复杂度：O(n)
  • 空间复杂度：O(n)

优化空间复杂度，由于dp[i]便是由前两位推出来的，那么也不必dp数组了，C++代码如下：

// 版别二
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int dp0 = cost[0];
        int dp1 = cost[1];
        for (int i = 2; i < cost.size(); i++) {
            int dpi = min(dp0, dp1) + cost[i];
            dp0 = dp1; // 记录一下前两位
            dp1 = dpi;
        }
        return min(dp0, dp1);
    }
};
  • 时刻复杂度：O(n)
  • 空间复杂度：O(1)

一般像第一个版别的算法，都会有这样的第二个版别，可是不主张第二版别，鞋底版别直观简洁。

4.3 js代码

var minCostClimbingStairs = function(cost) {
    const 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])
};

4.4 拓宽

标题描绘为：每逢你爬上一个阶梯你都要花费对应的膂力值，一旦支付了相应的膂力值，你就能够挑选向上爬一个阶梯或许爬两个阶梯。

示例1：

输入：cost = [10, 15, 20] 输出：15

从标题描绘能够看出：要不是第一步不需求花费膂力，要不便是第最终一步不需求花费膂力，我个人了解：题意说的其实是第一步是要支付费用的！ 。由于是当你爬上一个台阶就要花费对应的膂力值！

所以我界说的dp[i]意思是也是第一步是要花费膂力的，最终一步不必花费膂力了，由于已经支付了。

当然也能够样，界说dp[i]为:第一步是不花费膂力，最终一步是花费膂力的

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()];
    }
};

5 62 不同途径

力扣标题链接 一个机器人坐落一个 m x n网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或许向右移动一步。机器人试图抵达网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的途径？

动态规划Ⅱ（使用最小花费爬楼梯，不同路径）

5.1 深搜

最直观的主意便是用图论里的深搜，来枚举出来有多少种途径。

留意标题中说机器人每次只能向下或许向右移动一步，那么其实机器人走过的途径能够笼统为一棵二叉树，而叶子节点便是终点！

如图举例：

动态规划Ⅱ（使用最小花费爬楼梯，不同路径）

此时问题就能够转化为求二叉树叶子节点的个数，代码如下：

class Solution {
private:
    int dfs(int i, int j, int m, int n) {
        if (i > m || j > n) return 0; // 越界了
        if (i == m && j == n) return 1; // 找到一种办法，相当于找到了叶子节点
        return dfs(i + 1, j, m, n) + dfs(i, j + 1, m, n);
    }
public:
    int uniquePaths(int m, int n) {
        return dfs(1, 1, m, n);
    }
};

提交了代码会发现超时了！！ 分析一下时刻复杂度：这个深搜的算法，便是遍历整个二叉树(其实没有遍历整个二叉树，仅仅近似罢了) 深度：m+n-1(深度从1开端计算)

那二叉树的节点个数便是2^(m+n-1)-1 所以：时刻复杂度为O(2^(m+n-1)-1) 非常大

5.2 动态规划

机器人从(0 , 0) 方位动身，到(m – 1, n – 1)终点。

五部曲：

1 确认dp数组和下标意义 dp[i][j]:表明从(0,0)动身，到(i,j)有dp[i][j]条不同的途径

2 确认递推公式 想求dp[i][j]，只能有两个方向来推导，即dp[i-1][j]和dp[i][j-1]。 dp[i-1][j]：表明从(0,0)的方位到(i-1,j)，dp[i][j-1]同理 那么：dp[i][j] = dp[i-1][j] + dp[i][j-1]

3 dp数组的初始化

首先dp[i][0] 必定都是1，由于从(0,0)方位到(i,0)的途径只要一条 ，那么dp[0][j]同理 初始化代码： for(int i = 0; i < m; i++) dp[i][0] = 1; for(int j = 0; j < n; i++) dp[0][j] = 1;

4 确认遍历次序 递归公式dp[i][j] = dp[i – 1][j] + dp[i][j – 1]，dp[i][j]都是从其上方和左方推导而来，那么从左到右一层一层遍历就能够了。这样就能够保证推导dp[i][j]的时分，dp[i – 1][j] 和 dp[i][j – 1]必定是有数值的。

5 举例推导dp数组 如图：

动态规划Ⅱ（使用最小花费爬楼梯，不同路径）

cpp代码：

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for (int i = 0; i < m; i++) dp[i][0] = 1;
        for (int j = 0; j < n; j++) dp[0][j] = 1;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
};
  • 时刻复杂度：O(m n)
  • 空间复杂度：O(m n)

其实用一个一维数组（也能够了解是滚动数组）就能够了，可是不利于了解，能够优化点空间，主张先了解了二维，再了解一维，C++代码如下：

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> dp(n);
        for (int i = 0; i < n; i++) dp[i] = 1;
        for (int j = 1; j < m; j++) {
            for (int i = 1; i < n; i++) {
                dp[i] += dp[i - 1];
            }
        }
        return dp[n - 1];
    }
};
  • 时刻复杂度：O(m n)
  • 空间复杂度：O(n)

5.3 数论办法

在这个图中，能够看出总共m，n的话，无论怎么走，走到终点都需求 m + n – 2 步。

动态规划Ⅱ（使用最小花费爬楼梯，不同路径）

在这m + n – 2 步中，必定有 m – 1 步是要向下走的，不必管什么时分向下走。

那么有几种走法呢？ 能够转化为，给你m + n – 2个不同的数，随便取m – 1个数，有几种取法。

那么这便是一个组合问题了。

动态规划Ⅱ（使用最小花费爬楼梯，不同路径）

求组合的时分，要避免两个int相乘溢出！ 所以不能把算式的分子都算出来，分母都算出来再做除法。

需求在计算分子的时分，不断除以分母，代码如下：

class Solution {
public:
    int uniquePaths(int m, int n) {
        long long numerator = 1; // 分子
        int denominator = m - 1; // 分母
        int count = m - 1;
        int t = m + n - 2;
        while (count--) {
            numerator *= (t--);
            while (denominator != 0 && numerator % denominator == 0) {
                numerator /= denominator;
                denominator--;
            }
        }
        return numerator;
    }
};
  • 时刻复杂度：O(m)
  • 空间复杂度：O(1)

计算组合问题的代码仍是有难度的，特别是处理溢出的情况！

5.4 js代码

var uniquePaths = function(m, n) {
    const dp = Array(m).fill().map(item => Array(n))
    for (let i = 0; i < m; ++i) {
        dp[i][0] = 1
    }
    for (let i = 0; i < n; ++i) {
        dp[0][i] = 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]
        }
    }
    return dp[m - 1][n - 1]
};

版别二：

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    let dp = new Array(m).fill(1).map(() => new Array(n).fill(1));
    // dp[i][j] 表明抵达（i，j） 点的途径数
    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];
        }
    }
    return dp[m-1][n-1];
};

总结：

动规的五部曲：

  1. 确认dp数组（dp table）以及下标的意义
  2. 确认递推公式
  3. dp数组怎么初始化
  4. 确认遍历次序
  5. 举例推导dp数组

假如代码写出来了，一直AC不了，灵魂三问：

  1. 这道标题我举例推导状态转移公式了么？
  2. 我打印dp数组的日志了么？
  3. 打印出来了dp数组和我想的一样么？

哈哈，专治各种代码写出来了但AC不了的疑难杂症。