算法（三）动态规划

1. 简介

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

斐波那契数列

$$F=\left\{\begin{array}{c}0, \mathrm{n}=0 \\ 1, \mathrm{n}=1 \\ \text { Fibonacci }[n-1]+\text { Fibonacci }[n-2], n>1\end{array}\right.$$

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

动态规划 VS 分而治之

相同点：都是将问题拆为多个小问题

不同点：动态规划的小问题是相互有联系的，而分而治之是相互独立的

2. 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，执行上述公式

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

优化：

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;
};

198. 打家劫舍

解题思路：

$$\left\{\begin{array}{ll}d p[0]=n u m s[0] & \text { 只有一间房屋，则偷窃该房屋 } \\ d p[1]=\max (\text { nums }[0], n u m s[1]) & \text { 只有两间房屋，选择其中金额较高的房屋进行偷窃 }\end{array}\right.$$

• 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，执行上述公式

var rob = function (nums) {
    if (!nums.length) 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
};