【进阶篇 - Day 37】 2020-12-07 -动态规划系列（07. 高频面试题 ）

题目描述

入选理由

1. 面试考察的重点题型

题目描述

70. 爬楼梯 (opens new window) > 62. 不同路径 (opens new window) > 121. 买卖股票的最佳时机 (opens new window) > 122. 买卖股票的最佳时机 II (opens new window) > 123. 买卖股票的最佳时机 III (opens new window) > 188. 买卖股票的最佳时机 IV (opens new window) > 309. 最佳买卖股票时机含冷冻期 (opens new window) > 714. 买卖股票的最佳时机含手续费 (opens new window)

注意事项

高频系列的题目不要求大家全部做完，做你自己觉得有代表性的题目就好，毕竟不是人人都是西法，可以一秒 5 连鞭 如果碰到不会的题型，比如动态规划，后面会有专题进行讲解的，可以先标记一下，后面学了专题再回来解题

我的回答

https://github.com/leetcode-pp/91alg-2/issues/63#issuecomment-741547306

// TODO: 动态规划

爬楼梯

时空复杂度

时间复杂度：O(n)

空间复杂度: O(n)

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

不同路径

时间复杂度：O(n*m)

空间复杂度: O(n*m)

路径数 等于 能到左边的路径数加能到上边的路径数

var uniquePaths = function (m, n) {
    let dp = Array(m + 1).fill(Array(n + 1).fill(0))
    dp[1][1] = 1
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
        }
    }
    return dp[m][n]
};

买卖股票的最佳时机 ①

时间复杂度：O(n)

空间复杂度: O(1)

找到最低点，不断的用当前点和最低点比较，就能获得最大收益

var maxProfit = function (prices) {
    let max = 0
    let min = Infinity
    for (let i = 0; i < prices.length; i++) {
        min = Math.min(prices[i], min)
        max = Math.max(prices[i] - min, max)
    }
    return max
};

参考回答

• [官方题解](https://github.com/leetcode-pp/91alg-2/blob/master/solution/advanced/d37 dp.md)