关于leetcode:用javascript分类刷leetcode3动态规划图文视频讲解

什么是动静布局

动静布局，英文：Dynamic Programming，简称 DP，将问题合成为互 相重叠的子问题，通过重复求解子问题来解决原问题就是动静布局，如果某一问题有很多重叠子问题，应用动静布局来解是比拟无效的。

求解动静布局的外围问题是穷举，然而这类问题穷举有点特地，因为这类问题 存在「重叠子问题」，如果暴力穷举的话效率会极其低下。动静布局问题肯定会 具备「最优子结构」，能力通过子问题的最值得到原问题的最值。另外，尽管动静布局的核心思想就是穷举求最值，然而问题能够变幻无穷，穷举所有可行解其实并不是一件容易的事，只有列出 正确的「状态转移方程」能力正确地穷举。重叠子问题、最优子结构、状态转移方程就是动静布局三要素

动静布局和其余算法的区别

1. 动静布局和分治的区别：动静布局和分治都有最优子结构，然而分治的子问题不重叠
2. 动静布局和贪婪的区别：动静布局中每一个状态肯定是由上一个状态推导进去的，这一点就辨别于贪婪，贪婪没有状态推导，而是从部分间接选最优解，所以它永远是部分最优，然而全局的解不肯定是最优的。
3. 动静布局和递归的区别：递归和回溯可能存在十分多的反复计算，动静布局能够用递归加记忆化的形式缩小不必要的反复计算

动静布局的解题办法

• 递归 + 记忆化(自顶向下)
• 动静布局（自底向上）

[外链图片转存中 …(img-2XygXnrR-1668751529822)]

解动静布局题目的步骤

1. 依据重叠子问题定义状态
2. 寻找最优子结构推导状态转移方程
3. 确定 dp 初始状态
4. 确定输入值

斐波那契的动静布局的解题思路

[外链图片转存中 …(img-994raFxo-1668751529824)]

动画过大，点击查看

暴力递归

// 暴力递归复杂度 O(2^n)
var fib = function (N) {if (N == 0) return 0;
    if (N == 1) return 1;
    return fib(N - 1) + fib(N - 2);
};

递归 + 记忆化

var fib = function (n) {const memo = {}; // 对已算出的后果进行缓存

    const helper = (x) => {if (memo[x]) return memo[x];
        if (x == 0) return 0;
        if (x == 1) return 1;
        memo[x] = helper(x - 1) + helper(x - 2);
        return memo[x];
    };

    return helper(n);
};

动静布局

const fib = (n) => {if (n <= 1) return n;
    const dp = [0, 1];
    for (let i = 2; i <= n; i++) {
        // 自底向上计算每个状态
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
};

滚动数组优化

const fib = (n) => {if (n <= 1) return n;
    // 滚动数组 dp[i]只和 dp[i-1]、dp[i-2]相干，只保护长度为 2 的滚动数组，一直替换数组元素
    const dp = [0, 1];
    let sum = null;
    for (let i = 2; i <= n; i++) {sum = dp[0] + dp[1];
        dp[0] = dp[1];
        dp[1] = sum;
    }
    return sum;
};

动静布局 + 降维，（降维能缩小空间复杂度，但不利于程序的扩大）

var fib = function (N) {if (N <= 1) {return N;}
    let prev2 = 0;
    let prev1 = 1;
    let result = 0;
    for (let i = 2; i <= N; i++) {
        result = prev1 + prev2; // 间接用两个变量就行
        prev2 = prev1;
        prev1 = result;
    }
    return result;
};

509. 斐波那契数（easy）

斐波那契数（通常用 F(n) 示意）造成的序列称为 斐波那契数列。该数列由 0 和 1 开始，前面的每一项数字都是后面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n – 1) + F(n – 2)，其中 n > 1
给定 n，请计算 F(n)。

示例 1：

输出：n = 2
输入：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：

输出：n = 3
输入：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3：

输出：n = 4
输入：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提醒：

0 <= n <= 30

办法 1. 动静布局

• 思路：自底而上的动静布局
• 复杂度剖析：工夫复杂度O(n)，空间复杂度O(1)

Js:

var fib = function (N) {if (N <= 1) {return N;}
    let prev2 = 0;
    let prev1 = 1;
    let result = 0;
    for (let i = 2; i <= N; i++) {
        result = prev1 + prev2;
        prev2 = prev1;
        prev1 = result;
    }
    return result;
};

152. 乘积最大子数组（medium）

给你一个整数数组 nums，请你找出数组中乘积最大的非空间断子数组（该子数组中至多蕴含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32- 位 整数。

子数组 是数组的间断子序列。

示例 1:

输出: nums = [2,3,-2,4]
输入: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:

输出: nums = [-2,0,-1]
输入: 0
解释: 后果不能为 2, 因为 [-2,-1] 不是子数组。

提醒:

1 <= nums.length <= 2 * 104
-10 <= nums[i] <= 10
nums 的任何前缀或后缀的乘积都 保障 是一个 32- 位 整数

办法 1. 动静布局

[外链图片转存中 …(img-AoZLaTJl-1668751529826)]

• 思路：

  1. 状态定义：dp[i][0]示意从第 0 项到第 i 项范畴内的子数组的最小乘积，dp[i][1]示意从第 0 项到第 i 项范畴内的子数组的最大乘积
  2. 初始状态：dp[0][0]=nums[0], dp[0][1]=nums[0]

  3. 分状况探讨:

     • 不和他人乘，就 nums[i]本人
     • num[i] 是正数，心愿乘上后面的最大积
     • num[i] 是负数，心愿乘上后面的最小积

  4. 状态转移方程：

     • dp[i] [0]=min(dp[i−1] [0]∗num[i] , dp[i−1] [1] ∗ num[i], num[i])
     • dp[i] [1]=max(dp[i−1] [0]∗num[i] , dp[i−1] [1] ∗ num[i], num[i])
  5. 状态压缩：dp[i][x]只与dp[i][x]-1，所以只需定义两个变量，prevMin = nums[0]，prevMax = nums[0]

  6. 状态压缩之后的方程：

     • prevMin = Math.min(prevMin num[i], prevMax num[i], nums[i])
     • prevMax = Math.max(prevMin num[i], prevMax num[i], nums[i])
• 复杂度：工夫复杂度O(n)，空间复杂度O(1)

js:

var maxProduct = (nums) => {let res = nums[0]
    let prevMin = nums[0]
    let prevMax = nums[0]
    let temp1 = 0, temp2 = 0
    for (let i = 1; i < nums.length; i++) {temp1 = prevMin * nums[i]
        temp2 = prevMax * nums[i]
        prevMin = Math.min(temp1, temp2, nums[i])
        prevMax = Math.max(temp1, temp2, nums[i])
        res = Math.max(prevMax, res)
    }
    return res
}

62. 不同门路（medium）

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start”）。

机器人每次只能向下或者向右挪动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的门路？

[外链图片转存中 …(img-fClm1tNL-1668751529829)]

示例 1：

输出：m = 3, n = 7
输入：28
示例 2：

输出：m = 3, n = 2
输入：3
解释：
从左上角开始，总共有 3 条门路能够达到右下角。

1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

输出：m = 7, n = 3
输入：28
示例 4：

输出：m = 3, n = 3
输入：6

提醒：

1 <= m, n <= 100
题目数据保障答案小于等于 2 * 109

办法 1. 动静布局

动画过大，点击查看

• 思路: 因为在每个地位只能向下或者向右，所以每个坐标的门路和等于上一行雷同地位和上一列雷同地位不同门路的总和，状态转移方程：f[i][j] = f[i - 1][j] + f[i][j - 1];
• 复杂度: 工夫复杂度O(mn)。空间复杂度O(mn)，优化后O(n)

js:

var uniquePaths = function (m, n) {const f = new Array(m).fill(0).map(() => new Array(n).fill(0)); // 初始 dp 数组
    for (let i = 0; i < m; i++) {
        // 初始化列
        f[i][0] = 1;
    }
    for (let j = 0; j < n; j++) {
        // 初始化行
        f[0][j] = 1;
    }
    for (let i = 1; i < m; i++) {for (let j = 1; j < n; j++) {f[i][j] = f[i - 1][j] + f[i][j - 1];
        }
    }
    return f[m - 1][n - 1];
};

// 状态压缩
var uniquePaths = function (m, n) {let cur = new Array(n).fill(1);
    for (let i = 1; i < m; i++) {for (let r = 1; r < n; r++) {cur[r] = cur[r - 1] + cur[r];
        }
    }
    return cur[n - 1];
};

343. 整数拆分 (medium)

给定一个正整数 n，将其拆分为 k 个 正整数 的和（k >= 2），并使这些整数的乘积最大化。

返回 你能够取得的最大乘积。

示例 1:

输出: n = 2
输入: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:

输出: n = 10
输入: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

提醒:

2 <= n <= 58

[外链图片转存中 …(img-Fl0ZHFRt-1668751529831)]

• 思路：dp[i]为正整数 i 拆分之后的最大乘积，循环数字 n，对每个数字进行拆分，取最大的乘积，状态转移方程：dp[i] = Math.max(dp[i], dp[i - j] * j, (i - j) * j)，j*(i-j)示意把 i 拆分为 j 和 i - j 两个数相乘，j * dp[i-j]示意把 i 拆分成 j 和持续把 (i-j) 这个数拆分，取 (i-j) 拆分后果中的最大乘积与 j 相乘
• 复杂度：工夫复杂度 O(n^2)，两层循环。空间复杂度O(n)，dp 数组的空间

js：

var integerBreak = function (n) {//dp[i]为正整数 i 拆分之后的最大乘积
    let dp = new Array(n + 1).fill(0);
    dp[2] = 1;

    for (let i = 3; i <= n; i++) {for (let j = 1; j < i; j++) {//j*(i-j)示意把 i 拆分为 j 和 i - j 两个数相乘
            //j*dp[i-j]示意把 i 拆分成 j 和持续把 (i-j) 这个数拆分，取 (i-j) 拆分后果中的最大乘积与 j 相乘
            dp[i] = Math.max(dp[i], dp[i - j] * j, (i - j) * j);
        }
    }
    return dp[n];
};

10. 正则表达式匹配(hard)

给你一个字符串 s 和一个字符法则 p，请你来实现一个反对 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个后面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s 的，而不是局部字符串。

示例 1：

输出：s = “aa”, p = “a”
输入：false
解释：”a” 无奈匹配 “aa” 整个字符串。
示例 2:

输出：s = “aa”, p = “a*”
输入：true
解释：因为 ‘*’ 代表能够匹配零个或多个后面的那一个元素, 在这里后面的元素就是 ‘a’。因而，字符串 “aa” 可被视为 ‘a’ 反复了一次。
示例 3：

输出：s = “ab”, p = “.*”
输入：true
解释：”.” 示意可匹配零个或多个（’‘）任意字符（’.’）。

提醒：

1 <= s.length <= 20
1 <= p.length <= 30
s 只蕴含从 a-z 的小写字母。
p 只蕴含从 a-z 的小写字母，以及字符 . 和 *。
保障每次呈现字符 * 时，后面都匹配到无效的字符

办法 1. 动静布局

[外链图片转存中 …(img-ASizBFcM-1668751529832)]

[外链图片转存中 …(img-C7aglLUG-1668751529835)]

• 思路：dp[i][j] 示意 s 的前 i 个字符是否和 p 的前 j 个字符匹配，分为四种状况，看图
• 复杂度：工夫复杂度O(mn)，m,n 别离是字符串 s 和 p 的长度，须要嵌套循环 s 和 p。空间复杂度O(mn)，dp 数组所占的空间

js:

//dp[i][j]示意 s 的前 i 个字符是否和 p 的前 j 个字符匹配
const isMatch = (s, p) => {if (s == null || p == null) return false;// 极其状况 s 和 p 都是空 返回 false

    const sLen = s.length, pLen = p.length;

    const dp = new Array(sLen + 1);// 因为地位是从 0 开始的，第 0 个地位是空字符串 所以初始化长度是 sLen + 1
    for (let i = 0; i < dp.length; i++) {// 初始化 dp 数组
        dp[i] = new Array(pLen + 1).fill(false); // 将项默认为 false
    }
    // base case s 和 p 第 0 个地位是匹配的
    dp[0][0] = true;
    for (let j = 1; j < pLen + 1; j++) {// 初始化 dp 的第一列，此时 s 的地位是 0
        // 状况 1: 如果 p 的第 j - 1 个地位是 *，则 j 的状态等于 j - 2 的状态
        // 例如：s=''p='a*' 相当于 p 向前看 2 个地位如果匹配，则 * 相当于反复 0 个字符
        if (p[j - 1] == "*") dp[0][j] = dp[0][j - 2];
    }
    // 迭代
    for (let i = 1; i < sLen + 1; i++) {for (let j = 1; j < pLen + 1; j++) {// 状况 2: 如果 s 和 p 以后字符是相等的 或者 p 以后地位是. 则以后的 dp[i][j] 可由 dp[i - 1][j - 1]转移过去
            // 以后地位相匹配，则 s 和 p 都向前看一位 如果后面所有字符相匹配 则以后地位后面的所有字符也匹配
            // 例如：s='XXXa' p='XXX.' 或者 s='XXXa' p='XXXa'
            if (s[i - 1] == p[j - 1] || p[j - 1] == ".") {dp[i][j] = dp[i - 1][j - 1];
            } else if (p[j - 1] == "*") {// 状况 3: 进入以后字符不匹配的分支 如果以后 p 是 * 则有可能会匹配
                // s 以后地位和 p 前一个地位雷同 或者 p 前一个地位等于. 则有三种可能
                // 其中一种状况能匹配 则以后地位的状态也能匹配
                //dp[i][j - 2]：p 向前看 2 个地位，相当于 * 反复了 0 次，//dp[i][j - 1]：p 向前看 1 个地位，相当于 * 反复了 1 次
                //dp[i - 1][j]：s 向前看一个地位，相当于 * 反复了 n 次
                // 例如 s='XXXa' p='XXXa*'
                if (s[i - 1] == p[j - 2] || p[j - 2] == ".") {dp[i][j] = dp[i][j - 2] || dp[i][j - 1] || dp[i - 1][j];
                } else {
                    // 状况 4:s 以后地位和 p 前 2 个地位不匹配，则相当于 * 反复了 0 次
                    // 例如 s='XXXb' p='XXXa*' 以后地位的状态和 p 向前看 2 个地位的状态雷同
                    dp[i][j] = dp[i][j - 2];
                }
            }
        }
    }
    return dp[sLen][pLen]; // 长为 sLen 的 s 串 是否匹配 长为 pLen 的 p 串
};

63. 不同门路 II（medium）

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start”）。

机器人每次只能向下或者向右挪动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

当初思考网格中有障碍物。那么从左上角到右下角将会有多少条不同的门路？

网格中的障碍物和空地位别离用 1 和 0 来示意。

示例 1：

[外链图片转存中 …(img-OdFnEzw2-1668751529837)]

输出：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输入：2
解释：3×3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的门路：

1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

[外链图片转存中 …(img-NYTr6HDQ-1668751529839)]

输出：obstacleGrid = [[0,1],[0,0]]
输入：1

提醒：

m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGridi 为 0 或 1

办法 1. 动静布局

• 思路：和 62 题一样，区别就是遇到阻碍间接返回 0
• 复杂度：工夫复杂度O(mn)，空间复杂度O(mn)，状态压缩之后是 o(n)

Js:

var uniquePathsWithObstacles = function (obstacleGrid) {
    const m = obstacleGrid.length;
    const n = obstacleGrid[0].length;
    const dp = Array(m)
        .fill()
        .map((item) => Array(n).fill(0)); // 初始 dp 数组

    for (let i = 0; i < m && obstacleGrid[i][0] === 0; ++i) {
        // 初始列
        dp[i][0] = 1;
    }

    for (let i = 0; i < n && obstacleGrid[0][i] === 0; ++i) {
        // 初始行
        dp[0][i] = 1;
    }

    for (let i = 1; i < m; ++i) {for (let j = 1; j < n; ++j) {
            // 遇到阻碍间接返回 0
            dp[i][j] = obstacleGrid[i][j] === 1 ? 0 : dp[i - 1][j] + dp[i][j - 1];
        }
    }

    return dp[m - 1][n - 1];
};

// 状态压缩
var uniquePathsWithObstacles = function (obstacleGrid) {
    let m = obstacleGrid.length;
    let n = obstacleGrid[0].length;
    let dp = Array(n).fill(0); // 用 0 填充，因为当初有障碍物，以后 dp 数组元素的值还和 obstacleGrid[i][j]无关
    dp[0] = 1; // 第一列 临时用 1 填充
    for (let i = 0; i < m; i++) {for (let j = 0; j < n; j++) {if (obstacleGrid[i][j] == 1) {// 留神条件，遇到障碍物 dp[j]就变成 0，这里蕴含了第一列的状况
                dp[j] = 0;
            } else if (j > 0) {
                // 只有当 j >0 不是第一列了能力取到 j - 1
                dp[j] += dp[j - 1];
            }
        }
    }
    return dp[n - 1];
};

72. 编辑间隔（hard）

给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所应用的起码操作数。

你能够对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

示例 1：

输出：word1 = “horse”, word2 = “ros”
输入：3
解释：
horse -> rorse (将 ‘h’ 替换为 ‘r’)
rorse -> rose (删除 ‘r’)
rose -> ros (删除 ‘e’)
示例 2：

输出：word1 = “intention”, word2 = “execution”
输入：5
解释：
intention -> inention (删除 ‘t’)
inention -> enention (将 ‘i’ 替换为 ‘e’)
enention -> exention (将 ‘n’ 替换为 ‘x’)
exention -> exection (将 ‘n’ 替换为 ‘c’)
exection -> execution (插入 ‘u’)

提醒：

0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成

办法 1. 动静布局

[外链图片转存中 …(img-MbCCHo7z-1668751529840)]

[外链图片转存中 …(img-Fh36PrPn-1668751529842)]

• 思路：dp[i][j] 示意 word1 前 i 个字符和 word2 前 j 个字符的起码编辑间隔。

  1. 如果word1[i-1] === word2[j-1], 阐明最初一个字符不必操作，此时dp[i][j] = dp[i-1][j-1]，即此时的最小操作数和 word1 和 word2 都缩小一个字符的最小编辑数雷同

  2. 如果word1[i-1] !== word2[j-1]，则分为三种状况

     1. word1 删除最初一个字符，状态转移成dp[i-1][j]，即dp[i][j] = dp[i-1][j] + 1，+ 1 指删除操作
     2. word1 在最初加上一个字符，状态转移成dp[i][j-1]，即dp[i][j] = dp[i][j-1] + 1，+ 1 指减少操作
     3. word1 替换最初一个字符，状态转移成dp[i-1][j-1]，即 dp[i] [j] = dp[i-1] [j-1] + 1，+ 1 指替换操作
• 复杂度：工夫复杂度是O(mn)，m 是 word1 的长度，n 是 word2 的长度。空间复杂度是O(mn)，须要用 m * n 大小的二维数字存储状态。

Js:

const minDistance = (word1, word2) => {let dp = Array.from(Array(word1.length + 1), () => Array(word2.length + 1).fill(0));

    // 初始化数组，word1 前 i 个字符起码须要 i 次操作，比方 i 次删除变成 word2
    for (let i = 1; i <= word1.length; i++) {dp[i][0] = i;
    }

    // 初始化数组，word2 前 i 个字符起码须要 i 次操作，比方 j 次插入变成 word1
    for (let j = 1; j <= word2.length; j++) {dp[0][j] = j;
    }

    for (let i = 1; i <= word1.length; i++) {
        // 循环 word1 和 word2
        for (let j = 1; j <= word2.length; j++) {if (word1[i - 1] === word2[j - 1]) {// 如果 word1[i-1] === word2[j-1], 阐明最初一个字符不必操作。dp[i][j] = dp[i - 1][j - 1];
            } else {//dp[i-1][j] + 1：对应删除
                //dp[i][j-1] + 1：对应新增
                // dp[i-1][j-1] + 1：对应替换操作
                dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1);
            }
        }
    }

    return dp[word1.length][word2.length];
};

70. 爬楼梯（medium）

假如你正在爬楼梯。须要 n 阶你能力达到楼顶。

每次你能够爬 1 或 2 个台阶。你有多少种不同的办法能够爬到楼顶呢？

示例 1：

输出：n = 2
输入：2
解释：有两种办法能够爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输出：n = 3
输入：3
解释：有三种办法能够爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提醒：

1 <= n <= 45

办法 1. 动静布局

[外链图片转存中 …(img-y3TkSCIY-1668751529844)]

• 思路：因为每次能够爬 1 或 2 个台阶，所以到第 n 阶台阶能够从第 n - 2 或 n - 1 上来，其实就是斐波那契的 dp 方程
• 复杂度剖析：工夫复杂度O(n)，空间复杂度O(1)

Js:

var climbStairs = function (n) {const memo = [];
    memo[1] = 1;
    memo[2] = 2;
    for (let i = 3; i <= n; i++) {memo[i] = memo[i - 2] + memo[i - 1];// 所以到第 n 阶台阶能够从第 n - 2 或 n - 1 上来
    }
    return memo[n];
};

// 状态压缩
var climbStairs = (n) => {
    let prev = 1;
    let cur = 1;
    for (let i = 2; i < n + 1; i++) {[prev, cur] = [cur, prev + cur]
        // const temp = cur;   // 暂存上一次的 cur
        // cur = prev + cur;   // 以后的 cur = 上上次 cur + 上一次 cur
        // prev = temp;        // prev 更新为 上一次的 cur
    }
    return cur;
}

279. 齐全平方数 (medium)

给你一个整数 n，返回 和为 n 的齐全平方数的起码数量。

齐全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是齐全平方数，而 3 和 11 不是。

示例 1：

输出：n = 12
输入：3
解释：12 = 4 + 4 + 4
示例 2：

输出：n = 13
输入：2
解释：13 = 4 + 9

提醒：

1 <= n <= 104

[外链图片转存中 …(img-e5dNBtc1-1668751529847)]

办法 1: 动静布局

• 思路：dp[i] 示意 i 的齐全平方和的起码数量，dp[i - j * j] + 1示意减去一个齐全平方数 j 的齐全平方之后的数量加 1 就等于 dp[i]，只有在dp[i], dp[i - j * j] + 1 中寻找一个较少的就是最初 dp[i] 的值。

• 复杂度：工夫复杂度O(n* sqrt(n))，n 是输出的整数，须要循环 n 次，每次计算 dp 方程的复杂度sqrt(n)，空间复杂度 O(n)

js：

var numSquares = function (n) {const dp = [...Array(n)].map((_) => 0); // 初始化 dp 数组 当 n 为 0 的时候
    for (let i = 1; i <= n; i++) {dp[i] = i; // 最坏的状况就是每次 +1 比方: dp[3]=1+1+1
        for (let j = 1; i - j * j >= 0; j++) {// 枚举前一个状态
            dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // 动静转移方程
        }
    }
    return dp[n];
};

198. 打家劫舍（medium）

你是一个业余的小偷，打算偷窃沿街的屋宇。每间房内都藏有肯定的现金，影响你偷窃的惟一制约因素就是相邻的屋宇装有互相连通的防盗零碎，如果两间相邻的屋宇在同一早晨被小偷闯入，零碎会主动报警。

给定一个代表每个屋宇寄存金额的非负整数数组，计算你 不触动警报安装的状况下，一夜之内可能偷窃到的最高金额。

示例 1：

输出：[1,2,3,1]
输入：4
解释：偷窃 1 号屋宇 (金额 = 1)，而后偷窃 3 号屋宇 (金额 = 3)。

 偷窃到的最高金额 = 1 + 3 = 4。

示例 2：

输出：[2,7,9,3,1]
输入：12
解释：偷窃 1 号屋宇 (金额 = 2), 偷窃 3 号屋宇 (金额 = 9)，接着偷窃 5 号屋宇 (金额 = 1)。

 偷窃到的最高金额 = 2 + 9 + 1 = 12。

提醒：

1 <= nums.length <= 100
0 <= nums[i] <= 400

[外链图片转存中 …(img-teb9gEDd-1668751529849)]

• 思路：dp[i]示意 0 - i 能偷的最大金额，dp[i]由两种状况中的最大值转移过去

  1. dp[i - 2] + nums[i] 示意偷以后地位，那么 i - 1 的地位不能偷，而且须要加上dp[i-2], 也就是前 i - 2 个房间的金钱
  2. dp[i - 1]示意偷以后地位，只偷 i - 1 的房间
• 复杂度：工夫复杂度O(n)，遍历一次数组，空间复杂度O(1)，状态压缩之后是O(1)，没有状态压缩是O(n)

js：

//dp[i]示意 0 - i 能偷的最大金额
const rob = (nums) => {
    const len = nums.length;
    const dp = [nums[0], Math.max(nums[0], nums[1])]; // 初始化 dp 数组的前两项
    for (let i = 2; i < len; i++) {
        // 从第三个地位开始遍历
        //dp[i - 2] + nums[i] 示意偷以后地位，那么 i - 1 的地位不能偷，// 而且须要加上 dp[i-2], 也就是前 i - 2 个房间的金钱
        //dp[i - 1]示意偷以后地位，只偷 i - 1 的房间
        dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
    }
    return dp[len - 1]; // 返回最初最大的项
};

// 状态压缩
var rob = function (nums) {if(nums.length === 1) return nums[0]
    let len = nums.length;
    let dp_0 = nums[0],
        dp_1 = Math.max(nums[0], nums[1]);
    let dp_max = dp_1;
    for (let i = 2; i < len; i++) {
        dp_max = Math.max(
            dp_1, // 不抢以后家
            dp_0 + nums[i] // 抢以后家
        );
        dp_0 = dp_1; // 滚动替换变量
        dp_1 = dp_max;
    }
    return dp_max;
};

视频解说：传送门

什么是动静布局

动静布局，英文：Dynamic Programming，简称 DP，将问题合成为互 相重叠的子问题，通过重复求解子问题来解决原问题就是动静布局，如果某一问题有很多重叠子问题，应用动静布局来解是比拟无效的。

求解动静布局的外围问题是穷举，然而这类问题穷举有点特地，因为这类问题 存在「重叠子问题」，如果暴力穷举的话效率会极其低下。动静布局问题肯定会 具备「最优子结构」，能力通过子问题的最值得到原问题的最值。另外，尽管动静布局的核心思想就是穷举求最值，然而问题能够变幻无穷，穷举所有可行解其实并不是一件容易的事，只有列出 正确的「状态转移方程」能力正确地穷举。重叠子问题、最优子结构、状态转移方程就是动静布局三要素

动静布局和其余算法的区别

1. 动静布局和分治的区别：动静布局和分治都有最优子结构，然而分治的子问题不重叠
2. 动静布局和贪婪的区别：动静布局中每一个状态肯定是由上一个状态推导进去的，这一点就辨别于贪婪，贪婪没有状态推导，而是从部分间接选最优解，所以它永远是部分最优，然而全局的解不肯定是最优的。
3. 动静布局和递归的区别：递归和回溯可能存在十分多的反复计算，动静布局能够用递归加记忆化的形式缩小不必要的反复计算

动静布局的解题办法

• 递归 + 记忆化(自顶向下)
• 动静布局（自底向上）

解动静布局题目的步骤

1. 依据重叠子问题定义状态
2. 寻找最优子结构推导状态转移方程
3. 确定 dp 初始状态
4. 确定输入值

斐波那契的动静布局的解题思路

动画过大，点击查看

暴力递归

// 暴力递归复杂度 O(2^n)
var fib = function (N) {if (N == 0) return 0;
    if (N == 1) return 1;
    return fib(N - 1) + fib(N - 2);
};

递归 + 记忆化

var fib = function (n) {const memo = {}; // 对已算出的后果进行缓存

    const helper = (x) => {if (memo[x]) return memo[x];
        if (x == 0) return 0;
        if (x == 1) return 1;
        memo[x] = helper(x - 1) + helper(x - 2);
        return memo[x];
    };

    return helper(n);
};

动静布局

const fib = (n) => {if (n <= 1) return n;
    const dp = [0, 1];
    for (let i = 2; i <= n; i++) {
        // 自底向上计算每个状态
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
};

滚动数组优化

const fib = (n) => {if (n <= 1) return n;
    // 滚动数组 dp[i]只和 dp[i-1]、dp[i-2]相干，只保护长度为 2 的滚动数组，一直替换数组元素
    const dp = [0, 1];
    let sum = null;
    for (let i = 2; i <= n; i++) {sum = dp[0] + dp[1];
        dp[0] = dp[1];
        dp[1] = sum;
    }
    return sum;
};

动静布局 + 降维，（降维能缩小空间复杂度，但不利于程序的扩大）

var fib = function (N) {if (N <= 1) {return N;}
    let prev2 = 0;
    let prev1 = 1;
    let result = 0;
    for (let i = 2; i <= N; i++) {
        result = prev1 + prev2; // 间接用两个变量就行
        prev2 = prev1;
        prev1 = result;
    }
    return result;
};

509. 斐波那契数（easy）

斐波那契数（通常用 F(n) 示意）造成的序列称为 斐波那契数列。该数列由 0 和 1 开始，前面的每一项数字都是后面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n – 1) + F(n – 2)，其中 n > 1
给定 n，请计算 F(n)。

示例 1：

输出：n = 2
输入：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：

输出：n = 3
输入：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3：

输出：n = 4
输入：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提醒：

0 <= n <= 30

办法 1. 动静布局

• 思路：自底而上的动静布局
• 复杂度剖析：工夫复杂度O(n)，空间复杂度O(1)

Js:

var fib = function (N) {if (N <= 1) {return N;}
    let prev2 = 0;
    let prev1 = 1;
    let result = 0;
    for (let i = 2; i <= N; i++) {
        result = prev1 + prev2;
        prev2 = prev1;
        prev1 = result;
    }
    return result;
};

152. 乘积最大子数组（medium）

给你一个整数数组 nums，请你找出数组中乘积最大的非空间断子数组（该子数组中至多蕴含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32- 位 整数。

子数组 是数组的间断子序列。

示例 1:

输出: nums = [2,3,-2,4]
输入: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:

输出: nums = [-2,0,-1]
输入: 0
解释: 后果不能为 2, 因为 [-2,-1] 不是子数组。

提醒:

1 <= nums.length <= 2 * 104
-10 <= nums[i] <= 10
nums 的任何前缀或后缀的乘积都 保障 是一个 32- 位 整数

办法 1. 动静布局

• 思路：

  1. 状态定义：dp[i][0]示意从第 0 项到第 i 项范畴内的子数组的最小乘积，dp[i][1]示意从第 0 项到第 i 项范畴内的子数组的最大乘积
  2. 初始状态：dp[0][0]=nums[0], dp[0][1]=nums[0]

  3. 分状况探讨:

     • 不和他人乘，就 nums[i]本人
     • num[i] 是正数，心愿乘上后面的最大积
     • num[i] 是负数，心愿乘上后面的最小积

  4. 状态转移方程：

     • dp[i] [0]=min(dp[i−1] [0]∗num[i] , dp[i−1] [1] ∗ num[i], num[i])
     • dp[i] [1]=max(dp[i−1] [0]∗num[i] , dp[i−1] [1] ∗ num[i], num[i])
  5. 状态压缩：dp[i][x]只与dp[i][x]-1，所以只需定义两个变量，prevMin = nums[0]，prevMax = nums[0]

  6. 状态压缩之后的方程：

     • prevMin = Math.min(prevMin num[i], prevMax num[i], nums[i])
     • prevMax = Math.max(prevMin num[i], prevMax num[i], nums[i])
• 复杂度：工夫复杂度O(n)，空间复杂度O(1)

js:

var maxProduct = (nums) => {let res = nums[0]
    let prevMin = nums[0]
    let prevMax = nums[0]
    let temp1 = 0, temp2 = 0
    for (let i = 1; i < nums.length; i++) {temp1 = prevMin * nums[i]
        temp2 = prevMax * nums[i]
        prevMin = Math.min(temp1, temp2, nums[i])
        prevMax = Math.max(temp1, temp2, nums[i])
        res = Math.max(prevMax, res)
    }
    return res
}

62. 不同门路（medium）

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start”）。

机器人每次只能向下或者向右挪动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的门路？

示例 1：

输出：m = 3, n = 7
输入：28
示例 2：

输出：m = 3, n = 2
输入：3
解释：
从左上角开始，总共有 3 条门路能够达到右下角。

1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

输出：m = 7, n = 3
输入：28
示例 4：

输出：m = 3, n = 3
输入：6

提醒：

1 <= m, n <= 100
题目数据保障答案小于等于 2 * 109

办法 1. 动静布局

动画过大，点击查看

• 思路: 因为在每个地位只能向下或者向右，所以每个坐标的门路和等于上一行雷同地位和上一列雷同地位不同门路的总和，状态转移方程：f[i][j] = f[i - 1][j] + f[i][j - 1];
• 复杂度: 工夫复杂度O(mn)。空间复杂度O(mn)，优化后O(n)

js:

var uniquePaths = function (m, n) {const f = new Array(m).fill(0).map(() => new Array(n).fill(0)); // 初始 dp 数组
    for (let i = 0; i < m; i++) {
        // 初始化列
        f[i][0] = 1;
    }
    for (let j = 0; j < n; j++) {
        // 初始化行
        f[0][j] = 1;
    }
    for (let i = 1; i < m; i++) {for (let j = 1; j < n; j++) {f[i][j] = f[i - 1][j] + f[i][j - 1];
        }
    }
    return f[m - 1][n - 1];
};

// 状态压缩
var uniquePaths = function (m, n) {let cur = new Array(n).fill(1);
    for (let i = 1; i < m; i++) {for (let r = 1; r < n; r++) {cur[r] = cur[r - 1] + cur[r];
        }
    }
    return cur[n - 1];
};

343. 整数拆分 (medium)

给定一个正整数 n，将其拆分为 k 个 正整数 的和（k >= 2），并使这些整数的乘积最大化。

返回 你能够取得的最大乘积。

示例 1:

输出: n = 2
输入: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:

输出: n = 10
输入: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

提醒:

2 <= n <= 58

• 思路：dp[i]为正整数 i 拆分之后的最大乘积，循环数字 n，对每个数字进行拆分，取最大的乘积，状态转移方程：dp[i] = Math.max(dp[i], dp[i - j] * j, (i - j) * j)，j*(i-j)示意把 i 拆分为 j 和 i - j 两个数相乘，j * dp[i-j]示意把 i 拆分成 j 和持续把 (i-j) 这个数拆分，取 (i-j) 拆分后果中的最大乘积与 j 相乘
• 复杂度：工夫复杂度 O(n^2)，两层循环。空间复杂度O(n)，dp 数组的空间

js：

var integerBreak = function (n) {//dp[i]为正整数 i 拆分之后的最大乘积
    let dp = new Array(n + 1).fill(0);
    dp[2] = 1;

    for (let i = 3; i <= n; i++) {for (let j = 1; j < i; j++) {//j*(i-j)示意把 i 拆分为 j 和 i - j 两个数相乘
            //j*dp[i-j]示意把 i 拆分成 j 和持续把 (i-j) 这个数拆分，取 (i-j) 拆分后果中的最大乘积与 j 相乘
            dp[i] = Math.max(dp[i], dp[i - j] * j, (i - j) * j);
        }
    }
    return dp[n];
};

10. 正则表达式匹配(hard)

给你一个字符串 s 和一个字符法则 p，请你来实现一个反对 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个后面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s 的，而不是局部字符串。

示例 1：

输出：s = “aa”, p = “a”
输入：false
解释：”a” 无奈匹配 “aa” 整个字符串。
示例 2:

输出：s = “aa”, p = “a*”
输入：true
解释：因为 ‘*’ 代表能够匹配零个或多个后面的那一个元素, 在这里后面的元素就是 ‘a’。因而，字符串 “aa” 可被视为 ‘a’ 反复了一次。
示例 3：

输出：s = “ab”, p = “.*”
输入：true
解释：”.” 示意可匹配零个或多个（’‘）任意字符（’.’）。

提醒：

1 <= s.length <= 20
1 <= p.length <= 30
s 只蕴含从 a-z 的小写字母。
p 只蕴含从 a-z 的小写字母，以及字符 . 和 *。
保障每次呈现字符 * 时，后面都匹配到无效的字符

办法 1. 动静布局

• 思路：dp[i][j] 示意 s 的前 i 个字符是否和 p 的前 j 个字符匹配，分为四种状况，看图
• 复杂度：工夫复杂度O(mn)，m,n 别离是字符串 s 和 p 的长度，须要嵌套循环 s 和 p。空间复杂度O(mn)，dp 数组所占的空间

js:

//dp[i][j]示意 s 的前 i 个字符是否和 p 的前 j 个字符匹配
const isMatch = (s, p) => {if (s == null || p == null) return false;// 极其状况 s 和 p 都是空 返回 false

    const sLen = s.length, pLen = p.length;

    const dp = new Array(sLen + 1);// 因为地位是从 0 开始的，第 0 个地位是空字符串 所以初始化长度是 sLen + 1
    for (let i = 0; i < dp.length; i++) {// 初始化 dp 数组
        dp[i] = new Array(pLen + 1).fill(false); // 将项默认为 false
    }
    // base case s 和 p 第 0 个地位是匹配的
    dp[0][0] = true;
    for (let j = 1; j < pLen + 1; j++) {// 初始化 dp 的第一列，此时 s 的地位是 0
        // 状况 1: 如果 p 的第 j - 1 个地位是 *，则 j 的状态等于 j - 2 的状态
        // 例如：s=''p='a*' 相当于 p 向前看 2 个地位如果匹配，则 * 相当于反复 0 个字符
        if (p[j - 1] == "*") dp[0][j] = dp[0][j - 2];
    }
    // 迭代
    for (let i = 1; i < sLen + 1; i++) {for (let j = 1; j < pLen + 1; j++) {// 状况 2: 如果 s 和 p 以后字符是相等的 或者 p 以后地位是. 则以后的 dp[i][j] 可由 dp[i - 1][j - 1]转移过去
            // 以后地位相匹配，则 s 和 p 都向前看一位 如果后面所有字符相匹配 则以后地位后面的所有字符也匹配
            // 例如：s='XXXa' p='XXX.' 或者 s='XXXa' p='XXXa'
            if (s[i - 1] == p[j - 1] || p[j - 1] == ".") {dp[i][j] = dp[i - 1][j - 1];
            } else if (p[j - 1] == "*") {// 状况 3: 进入以后字符不匹配的分支 如果以后 p 是 * 则有可能会匹配
                // s 以后地位和 p 前一个地位雷同 或者 p 前一个地位等于. 则有三种可能
                // 其中一种状况能匹配 则以后地位的状态也能匹配
                //dp[i][j - 2]：p 向前看 2 个地位，相当于 * 反复了 0 次，//dp[i][j - 1]：p 向前看 1 个地位，相当于 * 反复了 1 次
                //dp[i - 1][j]：s 向前看一个地位，相当于 * 反复了 n 次
                // 例如 s='XXXa' p='XXXa*'
                if (s[i - 1] == p[j - 2] || p[j - 2] == ".") {dp[i][j] = dp[i][j - 2] || dp[i][j - 1] || dp[i - 1][j];
                } else {
                    // 状况 4:s 以后地位和 p 前 2 个地位不匹配，则相当于 * 反复了 0 次
                    // 例如 s='XXXb' p='XXXa*' 以后地位的状态和 p 向前看 2 个地位的状态雷同
                    dp[i][j] = dp[i][j - 2];
                }
            }
        }
    }
    return dp[sLen][pLen]; // 长为 sLen 的 s 串 是否匹配 长为 pLen 的 p 串
};

63. 不同门路 II（medium）

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start”）。

机器人每次只能向下或者向右挪动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

当初思考网格中有障碍物。那么从左上角到右下角将会有多少条不同的门路？

网格中的障碍物和空地位别离用 1 和 0 来示意。

示例 1：

输出：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输入：2
解释：3×3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的门路：

1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

输出：obstacleGrid = [[0,1],[0,0]]
输入：1

提醒：

m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGridi 为 0 或 1

办法 1. 动静布局

• 思路：和 62 题一样，区别就是遇到阻碍间接返回 0
• 复杂度：工夫复杂度O(mn)，空间复杂度O(mn)，状态压缩之后是 o(n)

Js:

var uniquePathsWithObstacles = function (obstacleGrid) {
    const m = obstacleGrid.length;
    const n = obstacleGrid[0].length;
    const dp = Array(m)
        .fill()
        .map((item) => Array(n).fill(0)); // 初始 dp 数组

    for (let i = 0; i < m && obstacleGrid[i][0] === 0; ++i) {
        // 初始列
        dp[i][0] = 1;
    }

    for (let i = 0; i < n && obstacleGrid[0][i] === 0; ++i) {
        // 初始行
        dp[0][i] = 1;
    }

    for (let i = 1; i < m; ++i) {for (let j = 1; j < n; ++j) {
            // 遇到阻碍间接返回 0
            dp[i][j] = obstacleGrid[i][j] === 1 ? 0 : dp[i - 1][j] + dp[i][j - 1];
        }
    }

    return dp[m - 1][n - 1];
};

// 状态压缩
var uniquePathsWithObstacles = function (obstacleGrid) {
    let m = obstacleGrid.length;
    let n = obstacleGrid[0].length;
    let dp = Array(n).fill(0); // 用 0 填充，因为当初有障碍物，以后 dp 数组元素的值还和 obstacleGrid[i][j]无关
    dp[0] = 1; // 第一列 临时用 1 填充
    for (let i = 0; i < m; i++) {for (let j = 0; j < n; j++) {if (obstacleGrid[i][j] == 1) {// 留神条件，遇到障碍物 dp[j]就变成 0，这里蕴含了第一列的状况
                dp[j] = 0;
            } else if (j > 0) {
                // 只有当 j >0 不是第一列了能力取到 j - 1
                dp[j] += dp[j - 1];
            }
        }
    }
    return dp[n - 1];
};

72. 编辑间隔（hard）

给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所应用的起码操作数。

你能够对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

示例 1：

输出：word1 = “horse”, word2 = “ros”
输入：3
解释：
horse -> rorse (将 ‘h’ 替换为 ‘r’)
rorse -> rose (删除 ‘r’)
rose -> ros (删除 ‘e’)
示例 2：

输出：word1 = “intention”, word2 = “execution”
输入：5
解释：
intention -> inention (删除 ‘t’)
inention -> enention (将 ‘i’ 替换为 ‘e’)
enention -> exention (将 ‘n’ 替换为 ‘x’)
exention -> exection (将 ‘n’ 替换为 ‘c’)
exection -> execution (插入 ‘u’)

提醒：

0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成

办法 1. 动静布局

• 思路：dp[i][j] 示意 word1 前 i 个字符和 word2 前 j 个字符的起码编辑间隔。

  1. 如果word1[i-1] === word2[j-1], 阐明最初一个字符不必操作，此时dp[i][j] = dp[i-1][j-1]，即此时的最小操作数和 word1 和 word2 都缩小一个字符的最小编辑数雷同

  2. 如果word1[i-1] !== word2[j-1]，则分为三种状况

     1. word1 删除最初一个字符，状态转移成dp[i-1][j]，即dp[i][j] = dp[i-1][j] + 1，+ 1 指删除操作
     2. word1 在最初加上一个字符，状态转移成dp[i][j-1]，即dp[i][j] = dp[i][j-1] + 1，+ 1 指减少操作
     3. word1 替换最初一个字符，状态转移成dp[i-1][j-1]，即 dp[i] [j] = dp[i-1] [j-1] + 1，+ 1 指替换操作
• 复杂度：工夫复杂度是O(mn)，m 是 word1 的长度，n 是 word2 的长度。空间复杂度是O(mn)，须要用 m * n 大小的二维数字存储状态。

Js:

const minDistance = (word1, word2) => {let dp = Array.from(Array(word1.length + 1), () => Array(word2.length + 1).fill(0));

    // 初始化数组，word1 前 i 个字符起码须要 i 次操作，比方 i 次删除变成 word2
    for (let i = 1; i <= word1.length; i++) {dp[i][0] = i;
    }

    // 初始化数组，word2 前 i 个字符起码须要 i 次操作，比方 j 次插入变成 word1
    for (let j = 1; j <= word2.length; j++) {dp[0][j] = j;
    }

    for (let i = 1; i <= word1.length; i++) {
        // 循环 word1 和 word2
        for (let j = 1; j <= word2.length; j++) {if (word1[i - 1] === word2[j - 1]) {// 如果 word1[i-1] === word2[j-1], 阐明最初一个字符不必操作。dp[i][j] = dp[i - 1][j - 1];
            } else {//dp[i-1][j] + 1：对应删除
                //dp[i][j-1] + 1：对应新增
                // dp[i-1][j-1] + 1：对应替换操作
                dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1);
            }
        }
    }

    return dp[word1.length][word2.length];
};

70. 爬楼梯（medium）

假如你正在爬楼梯。须要 n 阶你能力达到楼顶。

每次你能够爬 1 或 2 个台阶。你有多少种不同的办法能够爬到楼顶呢？

示例 1：

输出：n = 2
输入：2
解释：有两种办法能够爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输出：n = 3
输入：3
解释：有三种办法能够爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提醒：

1 <= n <= 45

办法 1. 动静布局

• 思路：因为每次能够爬 1 或 2 个台阶，所以到第 n 阶台阶能够从第 n - 2 或 n - 1 上来，其实就是斐波那契的 dp 方程
• 复杂度剖析：工夫复杂度O(n)，空间复杂度O(1)

Js:

var climbStairs = function (n) {const memo = [];
    memo[1] = 1;
    memo[2] = 2;
    for (let i = 3; i <= n; i++) {memo[i] = memo[i - 2] + memo[i - 1];// 所以到第 n 阶台阶能够从第 n - 2 或 n - 1 上来
    }
    return memo[n];
};

// 状态压缩
var climbStairs = (n) => {
    let prev = 1;
    let cur = 1;
    for (let i = 2; i < n + 1; i++) {[prev, cur] = [cur, prev + cur]
        // const temp = cur;   // 暂存上一次的 cur
        // cur = prev + cur;   // 以后的 cur = 上上次 cur + 上一次 cur
        // prev = temp;        // prev 更新为 上一次的 cur
    }
    return cur;
}

279. 齐全平方数 (medium)

给你一个整数 n，返回 和为 n 的齐全平方数的起码数量。

齐全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是齐全平方数，而 3 和 11 不是。

示例 1：

输出：n = 12
输入：3
解释：12 = 4 + 4 + 4
示例 2：

输出：n = 13
输入：2
解释：13 = 4 + 9

提醒：

1 <= n <= 104

办法 1: 动静布局

• 思路：dp[i] 示意 i 的齐全平方和的起码数量，dp[i - j * j] + 1示意减去一个齐全平方数 j 的齐全平方之后的数量加 1 就等于 dp[i]，只有在dp[i], dp[i - j * j] + 1 中寻找一个较少的就是最初 dp[i] 的值。

• 复杂度：工夫复杂度O(n* sqrt(n))，n 是输出的整数，须要循环 n 次，每次计算 dp 方程的复杂度sqrt(n)，空间复杂度 O(n)

js：

var numSquares = function (n) {const dp = [...Array(n)].map((_) => 0); // 初始化 dp 数组 当 n 为 0 的时候
    for (let i = 1; i <= n; i++) {dp[i] = i; // 最坏的状况就是每次 +1 比方: dp[3]=1+1+1
        for (let j = 1; i - j * j >= 0; j++) {// 枚举前一个状态
            dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // 动静转移方程
        }
    }
    return dp[n];
};

198. 打家劫舍（medium）

你是一个业余的小偷，打算偷窃沿街的屋宇。每间房内都藏有肯定的现金，影响你偷窃的惟一制约因素就是相邻的屋宇装有互相连通的防盗零碎，如果两间相邻的屋宇在同一早晨被小偷闯入，零碎会主动报警。

给定一个代表每个屋宇寄存金额的非负整数数组，计算你 不触动警报安装的状况下，一夜之内可能偷窃到的最高金额。

示例 1：

输出：[1,2,3,1]
输入：4
解释：偷窃 1 号屋宇 (金额 = 1)，而后偷窃 3 号屋宇 (金额 = 3)。

 偷窃到的最高金额 = 1 + 3 = 4。

示例 2：

输出：[2,7,9,3,1]
输入：12
解释：偷窃 1 号屋宇 (金额 = 2), 偷窃 3 号屋宇 (金额 = 9)，接着偷窃 5 号屋宇 (金额 = 1)。

 偷窃到的最高金额 = 2 + 9 + 1 = 12。

提醒：

1 <= nums.length <= 100
0 <= nums[i] <= 400

• 思路：dp[i]示意 0 - i 能偷的最大金额，dp[i]由两种状况中的最大值转移过去

  1. dp[i - 2] + nums[i] 示意偷以后地位，那么 i - 1 的地位不能偷，而且须要加上dp[i-2], 也就是前 i - 2 个房间的金钱
  2. dp[i - 1]示意偷以后地位，只偷 i - 1 的房间
• 复杂度：工夫复杂度O(n)，遍历一次数组，空间复杂度O(1)，状态压缩之后是O(1)，没有状态压缩是O(n)

js：

//dp[i]示意 0 - i 能偷的最大金额
const rob = (nums) => {
    const len = nums.length;
    const dp = [nums[0], Math.max(nums[0], nums[1])]; // 初始化 dp 数组的前两项
    for (let i = 2; i < len; i++) {
        // 从第三个地位开始遍历
        //dp[i - 2] + nums[i] 示意偷以后地位，那么 i - 1 的地位不能偷，// 而且须要加上 dp[i-2], 也就是前 i - 2 个房间的金钱
        //dp[i - 1]示意偷以后地位，只偷 i - 1 的房间
        dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
    }
    return dp[len - 1]; // 返回最初最大的项
};

// 状态压缩
var rob = function (nums) {if(nums.length === 1) return nums[0]
    let len = nums.length;
    let dp_0 = nums[0],
        dp_1 = Math.max(nums[0], nums[1]);
    let dp_max = dp_1;
    for (let i = 2; i < len; i++) {
        dp_max = Math.max(
            dp_1, // 不抢以后家
            dp_0 + nums[i] // 抢以后家
        );
        dp_0 = dp_1; // 滚动替换变量
        dp_1 = dp_max;
    }
    return dp_max;
};

视频解说：传送门