动态规划

• 动态规划是算法设计中的一种方法。
• 它将一个问题分解为互相重叠的子问题，通过反复求解子问题，来解决原来的问题。

斐波那契数列

• 定义子问题：F(n) = F(n -1) + F(n - 2)
• 反复执行：从2循环到n，执行上述公式。

动态规划vs分而治之

动态规划：子问题相互重叠 分而治之：子问题相互独立

LeetCode：70.爬楼梯

解题思路

• 爬到第 n 阶可以在 n - 1 阶爬 1 个台阶，或者在第 n - 2 阶爬 2 个台阶。
• F(n) = F(n - 1) + F(n - 2)

阶梯步骤

• 定义子问题：F(n) = F(n - 1) + F(n - 2)
• 反复执行：从 2 循环到 n，执行上述公式。

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if (n < 2) return 1;
    const dp = [1, 1]
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
};

优化

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if (n < 2) return 1;
    let dp0 = 1
    let dp1 = 1
    for (let i = 2; i <= n; i++) {
        const temp = dp0
        dp0 = dp1
        dp1 =  dp1 + temp
    }
    return dp1
};


70.爬楼梯
时间复杂度 O(n)
空间复杂度 O(n) 优化后是 O(1)

LeetCode：198.打家劫舍

解题思路

• f(k) = 从前 k 个房屋中能偷窃到的最大数额。
• Ak = 第 k 个房屋的钱数。
• f(k) = max(f(k - 2) + Ak，f(k - 1))

解题步骤

• 定义子问题：f(k) = max(f(k - 2) + Ak，f(k - 1))
• 反复执行：从 2 循环到 n，执行上述公式。

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    if (nums.length === 0) return 0
    const dp = [0, nums[0]]
    for (let i = 2; i <= nums.length; i++) {
        dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i -1])
    }
    return dp[nums.length]
};

优化后
/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    if (nums.length === 0) return 0
    let dp0 = 0
    let dp1 = nums[0]
    for (let i = 2; i <= nums.length; i++) {
        const dp2 = Math.max(dp0 + nums[i - 1], dp1)
        dp0 = dp1;
        dp1 = dp2
    }
    return dp1
};

198.打家劫舍
时间复杂度 O(n)
空间复杂度 O(n) 优化后是 O(1)