Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

70. 爬楼梯 #38

Open
Geekhyt opened this issue Feb 24, 2021 · 0 comments
Open

70. 爬楼梯 #38

Geekhyt opened this issue Feb 24, 2021 · 0 comments
Labels

Comments

@Geekhyt
Copy link
Owner

Geekhyt commented Feb 24, 2021

原题链接

虽然动态规划的最终版本 (降维再去维) 大都不是递归,但解题的过程还是离不开递归的。

如果你觉得你对递归理解的还不够透彻,请移步我的这篇专栏你真的懂递归吗?

新手可能会觉得动态规划思想接受起来比较难,确实,动态规划求解问题的过程不太符合人类常规的思维方式,我们需要切换成机器思维。

使用动态规划思想解题,首先要明确动态规划的三要素。

动态规划三要素

  • 重叠子问题
  • 最优子结构
  • 状态转移方程

重叠子问题

切换机器思维,自底向上思考。

爬第 n 阶楼梯的方法数量,等于两部分之和:

  • 爬上 n-1 阶楼梯的方法数量
  • 爬上 n-2 阶楼梯的方法数量

最优子结构

子问题的最优解能够推出原问题的优解。

状态转移方程

dp[n] = dp[n-1] + dp[n-2]

具备三要素,确认边界条件,初始化状态,开始切菜:

  • dp[0] = 1
  • dp[1] = 1
const climbStairs = function(n) {
    const dp = []
    dp[0] = 1
    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)

优化

在此基础上,我们还可以通过压缩空间来对算法进行优化。因为 dp[i] 只与 dp[i-1]dp[i-2] 有关,没有必要存储所有出现过的 dp 项,只用两个临时变量去存储这两个状态即可。

const climbStairs = function(n) {
    let a1 = 1
    let a2 = 1
    for (let i = 2; i <= n; i++) {
        [a1, a2] = [a2, a1 + a2]
    }
    return a2
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)
@Geekhyt Geekhyt added the 简单 label Jun 2, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant