什么是动静布局

动静布局，英文：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;};

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个字符的起码编辑间隔。

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

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
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 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];};

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