什么是动静布局
动静布局，英文：Dynamic Programming，简称 DP，将问题合成为互 相重叠的子问题，通过重复求解子问题来解决原问题就是动静布局，如果某一问题有很多重叠子问题，应用动静布局来解是比拟无效的。
求解动静布局的外围问题是穷举，然而这类问题穷举有点特地，因为这类问题 存在「重叠子问题」，如果暴力穷举的话效率会极其低下。动静布局问题肯定会 具备「最优子结构」，能力通过子问题的最值得到原问题的最值。另外，尽管动静布局的核心思想就是穷举求最值，然而问题能够变幻无穷，穷举所有可行解其实并不是一件容易的事，只有列出 正确的「状态转移方程」能力正确地穷举。重叠子问题、最优子结构、状态转移方程就是动静布局三要素
动静布局和其余算法的区别
- 动静布局和分治的区别：动静布局和分治都有最优子结构，然而分治的子问题不重叠
- 动静布局和贪婪的区别：动静布局中每一个状态肯定是由上一个状态推导进去的，这一点就辨别于贪婪，贪婪没有状态推导，而是从部分间接选最优解，所以它永远是部分最优，然而全局的解不肯定是最优的。
- 动静布局和递归的区别：递归和回溯可能存在十分多的反复计算，动静布局能够用递归加记忆化的形式缩小不必要的反复计算
动静布局的解题办法
- 递归 + 记忆化(自顶向下)
- 动静布局（自底向上）
解动静布局题目的步骤
- 依据重叠子问题定义状态
- 寻找最优子结构推导状态转移方程
- 确定 dp 初始状态
- 确定输入值
斐波那契的动静布局的解题思路
动画过大，点击查看
暴力递归
// 暴力递归复杂度 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;
};322. 零钱兑换 (medium)
视频解说：传送门
给你一个整数数组 coins，示意不同面额的硬币；以及一个整数 amount，示意总金额。
计算并返回能够凑成总金额所需的 起码的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你能够认为每种硬币的数量是有限的。
示例 1：
输出：coins = [1, 2, 5], amount = 11
输入：3
解释：11 = 5 + 5 + 1
示例 2：输出：coins = [2], amount = 3
输入：-1
示例 3：输出：coins = [1], amount = 0
输入：0提醒：
1 <= coins.length <= 12
1 <= coins[i] <= 231 – 1
0 <= amount <= 104
不能用贪婪做，反例，coins=[1, 3, 5, 6, 7]，amount=30，用贪婪先用最大的面额 7，在用 2 个 1，4 * 7 + 2 * 1 = 30，然而咱们用 5 个 6，5 * 6 = 30 就能用起码的硬币兑换实现
办法 1. 动静布局
- 思路：
dp[i]示意兑换面额i所须要的起码硬币，因为硬币有限，所以能够自底向上计算dp[i]，对于dp[0~i]的每个状态，循环coins数组，寻找能够兑换的组合，用i面额减去以后硬币价值，dp[i-coin]在加上一个硬币数就是dp[i], 最初取最小值就是答案，状态转移方程就是dp[i] = Math.min(dp[i], dp[i - coin] + 1); - 复杂度剖析：工夫复杂度是O(sn)，s 是兑换金额，n 是硬币数组长度，一共须要计算 s 个状态，每个状态须要遍历 n 个面额来转移状态。空间复杂度是
O(s)，也就是 dp 数组的长度
Js:
var coinChange = function (coins, amount) {let dp = new Array(amount + 1).fill(Infinity);// 初始化 dp 数组
dp[0] = 0;// 面额 0 只须要 0 个硬币兑换
for (let i = 1; i <= amount; i++) {// 循环面额
for (let coin of coins) {// 循环硬币数组
if (i - coin >= 0) {// 当面额大于硬币价值时
//dp[i - coin]：以后面额 i 减以后硬币价值所须要的起码硬币
//dp[i] 可由 dp[i - coin] + 1 转换而来
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];// 如果 dp[amount] === Infinity，则无奈兑换
};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 个字符的起码编辑间隔。- 如果
word1[i-1] === word2[j-1], 阐明最初一个字符不必操作，此时dp[i][j] = dp[i-1][j-1]，即此时的最小操作数和 word1 和 word2 都缩小一个字符的最小编辑数雷同 -
如果
word1[i-1] !== word2[j-1]，则分为三种状况- word1 删除最初一个字符，状态转移成
dp[i-1][j]，即dp[i][j] = dp[i-1][j] + 1，+ 1 指删除操作 - word1 在最初加上一个字符，状态转移成
dp[i][j-1]，即dp[i][j] = dp[i][j-1] + 1，+ 1 指减少操作 - word1 替换最初一个字符，状态转移成
dp[i-1][j-1]，即 dp[i] [j] = dp[i-1] [j-1] + 1，+ 1 指替换操作
- word1 删除最初一个字符，状态转移成
- 如果
- 复杂度：工夫复杂度是
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 阶
- 2 阶
示例 2：
输出：n = 3
输入：3
解释：有三种办法能够爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 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;
}120. 三角形最小门路和（medium）
视频解说：传送门
给定一个三角形 triangle，找出自顶向下的最小门路和。
每一步只能挪动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 雷同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于以后行的下标 i，那么下一步能够挪动到下一行的下标 i 或 i + 1。
示例 1：
输出：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输入：11
解释：如上面简图所示：
2
3 4
6 5 7
4 1 8 3
自顶向下的最小门路和为 11（即，2 + 3 + 5 + 1 = 11）。
示例 2：输出：triangle = [[-10]]
输入：-10提醒：
1 <= triangle.length <= 200
triangle[0].length == 1
triangle[i].length == triangle[i – 1].length + 1
-104 <= trianglei <= 104
办法 1. 动静布局
- 思路：从三角形最初一层开始向上遍历，每个数字的最小门路和是它上面两个数字中的较小者加上它自身
- 复杂度剖析：工夫复杂度
O(n^2)，空间简单O(n)
Js:
const minimumTotal = (triangle) => {
const h = triangle.length;
// 初始化 dp 数组
const dp = new Array(h);
for (let i = 0; i < h; i++) {dp[i] = new Array(triangle[i].length);
}
for (let i = h - 1; i >= 0; i--) { // 自底而上遍历
for (let j = 0; j < triangle[i].length; j++) { // 同一层的
if (i == h - 1) { // base case 最底层
dp[i][j] = triangle[i][j];
} else { // 状态转移方程，上一层由它上面一层计算出
dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j];
}
}
}
return dp[0][0];
};
// 状态压缩
const minimumTotal = (triangle) => {const bottom = triangle[triangle.length - 1];
const dp = new Array(bottom.length);
// base case 是最初一行
for (let i = 0; i < dp.length; i++) {dp[i] = bottom[i];
}
// 从倒数第二列开始迭代
for (let i = dp.length - 2; i >= 0; i--) {for (let j = 0; j < triangle[i].length; j++) {dp[j] = Math.min(dp[j], dp[j + 1]) + triangle[i][j];
}
}
return dp[0];
};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;
};312. 戳气球 (hard)
视频解说：传送门
有 n 个气球，编号为 0 到 n – 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
当初要求你戳破所有的气球。戳破第 i 个气球，你能够取得 nums[i – 1] nums[i] nums[i + 1] 枚硬币。这里的 i – 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i – 1 或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
求所能取得硬币的最大数量。
示例 1：
输出：nums = [3,1,5,8]
输入：167
解释：
nums = [3,1,5,8] –> [3,5,8] –> [3,8] –> [8] –> []
coins = 315 + 358 + 138 + 181 = 167
示例 2：输出：nums = [1,5]
输入：10提醒：
n == nums.length
1 <= n <= 300
0 <= nums[i] <= 100
办法 1: 动静布局
- 思路：
dp[i][j]示意开区间(i,j)能拿到的的金币，k 是这个区间 最初一个 被戳爆的气球，枚举i和j，遍历所有区间，i-j能取得的最大数量的金币等于 戳破以后的气球取得的金钱加上之前i-k、k-j区间中曾经取得的金币 - 复杂度：工夫复杂度
O(n^3)，n 是气球的数量，三层遍历。空间复杂度O(n^2)，dp 数组的空间。
js：
var maxCoins = function (nums) {
const n = nums.length;
let points = [1, ...nums, 1]; // 两边增加虚构气球
const dp = Array.from(Array(n + 2), () => Array(n + 2).fill(0)); //dp 数组初始化
// 自底向上转移状态
for (let i = n; i >= 0; i--) {
// i 一直减小
for (let j = i + 1; j < n + 2; j++) {
// j 不断扩大
for (let k = i + 1; k < j; k++) {
// 枚举 k 在 i 和 j 中的所有可能
//i- j 能取得的最大数量的金币等于 戳破以后的气球取得的金钱加上之前 i -k,k- j 区间中曾经取得的金币
dp[i][j] = Math.max(
// 挑战最大值
dp[i][j],
dp[i][k] + dp[k][j] + points[j] * points[k] * points[i]
);
}
}
}
return dp[0][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 条不同的门路：
- 向右 -> 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右 -> 向右
示例 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];
};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]由两种状况中的最大值转移过去dp[i - 2] + nums[i]示意偷以后地位，那么 i - 1 的地位不能偷，而且须要加上dp[i-2], 也就是前 i - 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;
};