leetcode每天5题-Day55-动态规划11. 斐波那契数2. 爬楼梯3. 使用最小花费爬楼梯4. 不同路径5. 不同路径 II

92 阅读 0 评论 61 点赞

我是靠谱客的博主有魅力路人，最近开发中收集的这篇文章主要介绍leetcode每天5题-Day55-动态规划11. 斐波那契数2. 爬楼梯3. 使用最小花费爬楼梯4. 不同路径5. 不同路径 II，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1. 斐波那契数

509. 斐波那契数-简单
b站视频讲解

递归

var fib = function(n) {
    if(n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
};

时间复杂度：O(2^n)
空间复杂度：O(n)

动规

动规五部曲;

确定dp数组（dp table）以及下标的含义
dp[i]的定义为：第i个数的斐波那契数值是dp[i]
确定递推公式
状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];
dp数组如何初始化
dp[0] = 1, dp[1] = 1;
确定遍历顺序
由于dp[i]是依赖于 dp[i - 1] 和 dp[i - 2]的，所以遍历顺序是从前向后
举例推导dp数组
如果代码写出来，发现结果不对，就把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];
};

时间复杂度：O(n)
空间复杂度：O(n)

优化：其实我们只需要维护两个数值就行了，不需要记录整个序列。

var fib = function(n) {
    if(n <= 1) return n;
    let p = 0, q = 1;
    for(let i = 2; i <= n; i++) {
        let sum = p + q;
        p = q;
        q = sum;
    }
    return q;
};

时间复杂度：O(n)
空间复杂度：O(1)

2. 爬楼梯

70. 爬楼梯-简单
讲解

动规五部曲;

确定dp数组（dp table）以及下标的含义
dp[i]的定义为：爬到第i层楼梯，有dp[i]种方法
确定递推公式
状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];
dp数组如何初始化
dp[1] = 1, dp[2] = 2;
确定遍历顺序
由于dp[i]是依赖于 dp[i - 1] 和 dp[i - 2]的，所以遍历顺序是从前向后
举例推导dp数组
如果代码写出来，发现结果不对，就把dp数组打印出来看看和我们推导的数列是不是一致的。

版本一

var climbStairs = function(n) {
    let dp = [1, 2];
    for(let i = 2; i < n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n - 1];
};

版本二

var climbStairs = function(n) {
    let p = 0, q = 0, r = 1;
    for (let i = 1; i <= n; ++i) {
        p = q;
        q = r;
        r = p + q;
    }
    return r;
};

拓展：一步一个台阶，两个台阶，三个台阶，直到 m个台阶，有多少种方法爬到n阶楼顶？

3. 使用最小花费爬楼梯

746. 使用最小花费爬楼梯-简单
讲解

动规五部曲;

确定dp数组（dp table）以及下标的含义
dp[i]的定义为：爬到第i层楼梯的最小花费
确定递推公式
有两个途径到达第i层楼梯，可以从i - 1或i - 2层楼梯上去。
状态转移方程 dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
dp数组如何初始化
dp[0] = 0, dp[1] = 0;
确定遍历顺序
由于dp[i]是依赖于 dp[i - 1] 和 dp[i - 2]的，所以遍历顺序是从前向后
举例推导dp数组
如果代码写出来，发现结果不对，就把dp数组打印出来看看和我们推导的数列是不是一致的。

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

4. 不同路径

62. 不同路径-中等
讲解

深搜

思路：机器人每次只能向下或者向右移动一步，那么其实机器人走过的路径可以抽象为一棵二叉树，而叶子节点就是终点。
时间复杂度为O(2^(m + n - 1) - 1)，指数级别。

动规

动规五部曲;

确定dp数组（dp table）以及下标的含义
dp[i][j]的定义为：机器人到达(i, j)位置时有 dp[i][j] 条不同路径数
确定递推公式
有两个途径到达(i, j)位置，可以从(i - 1, j)位置向下移动一步或(i, j - 1)位置向右移动一步。
状态转移方程 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
误区：从dp[i - 1][j]到dp[i][j]，路径数加一。从dp[i - 1][j]到dp[i][j]，只能向下走一步，所以路径数是不变得。dp[i][j - 1]同理。
dp数组如何初始化
dp[0][j] = 1, dp[i][0] = 1;
确定遍历顺序
遍历顺序是从上向下以及从左向右。

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

时间复杂度：O(m × n)
空间复杂度：O(m × n)

数论

在这个图中，可以看出一共m，n的话，无论怎么走，走到终点都需要 m + n - 2 步。其中一定有 m - 1 步是要向下走的，不用管什么时候向下走。问题转化为组合问题，给你m + n - 2个不同的数，随便取m - 1个数，有几种取法。

时间复杂度：O(m)
空间复杂度：O(1)

5. 不同路径 II

63. 不同路径 II-中等
讲解

与上题不同之处：当(i, j)为0时，也就是没有障碍时才进行递归。初始化不同，在首行/首列遇到障碍物就直接退出for循环了。

var uniquePathsWithObstacles = function(obstacleGrid) {
    let m = obstacleGrid.length, n = obstacleGrid[0].length;
    let dp = new Array(m).fill(0).map(() => new Array(n).fill(0));
    for(let i = 0; i < m && obstacleGrid[i][0] === 0; i++) dp[i][0] = 1;
    for(let j = 0; j < n && obstacleGrid[0][j] === 0; j++) dp[0][j] = 1;
    for(let i = 1; i < m; i++) {
        for(let j = 1; j < n; j++) {
            if(obstacleGrid[i][j] === 0) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
    }
    return dp[m - 1][n - 1];
};