动态规划刷题

按照算法和数据结构进行分类，一起来刷题，用于自己在面试前查漏补缺。我的意向岗位是前端，选择用javascript来刷题，优点是动态语言，语法简单，缺点是遇见复杂数据结构会出现较难的写法，如堆、并查集，每题对应leetcode的题号。本篇是动态规划

专题部分

动态规划

5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

1
2
3

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

1 2	输入：s = "cbbd" 输出："bb"

示例 3：

1 2	输入：s = "a" 输出："a"

示例 4：

1 2	输入：s = "ac" 输出："a"

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成

第i个字母到第j个字母的最大回文

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let n = s.length;
    if (n === 1) return s;
    let dp = new Array(n);
    let ans = "";
    for (let i = 0; i < n; i++) {
        dp[i] = new Array(n).fill(0);
    }
    for (let l = 0; l < n; l++) {
        for (let i = 0; i < n - 1; i++) {
            let j = i + l;
            if (j >= n) break;
            if (l === 0) {
                dp[i][j] = 1;
            } else if (l === 1) {
                dp[i][j] = s[i] === s[j] ? 1 : 0;
            } else {
                dp[i][j]  = (s[i] === s[j] && dp[i + 1][j - 1]);
            }
            if (dp[i][j] && l + 1 > ans.length) {
                ans = s.slice(i, j + 1);
            }
        }
    }
    return ans;
};

从中心开始两边拓展

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    if (s.length <= 1) return s;
    let res = "" + s[0];
    for (let i = 1; i < s.length; i++) {
        // 找到以 s[i] 为中心的回文串
        let temp1 = palindrome(s, i, i);
        // 找到以 s[i-1] 和 s[i] 为中心的回文串
        let temp2 = palindrome(s, i - 1, i);
        // 更新答案
        if (temp1.length > res.length) res = temp1;
        if (temp2.length > res.length) res = temp2;
    }
    return res;
};
function palindrome(s, l, r) {
    // 防止索引越界
    while (l >= 0 && r < s.length && s[l] === s[r]) {
        // 向两边展开
        l--; r++;
    }
    // 返回以 s[l] 和 s[r] 为中心的最长回文串
    return s.substr(l + 1, r - l - 1);
};

32. 最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

1
2
3

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：

1
2
3

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：

1 2	输入：s = "" 输出：0

提示：

0 <= s.length <= 3 * 104
s[i] 为 '(' 或 ')'

其实这道题动态规划并不是最好解法，但比较好想到

我们定义dp[i] 表示以下标 i 字符结尾的最长有效括号的长度。我们将 dp 数组全部初始化为 0 。显然有效的子串一定以 ‘)’ 结尾，因此我们可以知道以‘(’ 结尾的子串对应的 dp 值必定为 0 ，我们只需要求解 ‘)’ 在dp 数组中对应位置的值。

我们从前往后遍历字符串求解 dp 值，我们每两个字符检查一次：

1.s[i]=‘)’ 且 s[i−1]=‘(’，也就是字符串形如 “……()”，我们可以推出：
$$
\textit{dp}[i]=\textit{dp}[i-2]+2
$$
我们可以进行这样的转移，是因为结束部分的 “()” 是一个有效子字符串，并且将之前有效子字符串的长度增加了 2 。

2.s[i]=‘)’ 且 s[i−1]=‘)’，也就是字符串形如 “……))”，我们可以推出：
如果 s[i−dp[i−1]−1]=‘(’，那么
$$
\textit{dp}[i]=\textit{dp}[i-1]+\textit{dp}[i-\textit{dp}[i-1]-2]+2
$$
我们考虑如果倒数第二个 ‘)’ 是一个有效子字符串的一部分（记作 $$sub_s$$），对于最后一个 ‘)’ ，如果它是一个更长子字符串的一部分，那么它一定有一个对应的 ‘(’ ，且它的位置在倒数第二个 ‘)’ 所在的有效子字符串的前面（也就是 $$sub_s$$ 的前面）。因此，如果子字符串 $$sub_s$$ 的前面恰好是 ‘(’ ，那么我们就用 2 加上 $$sub_s$$ 的长度（dp[i−1]）去更新 dp[i]。同时，我们也会把有效子串 $$“(sub_s)”$$之前的有效子串的长度也加上，也就是再加上dp[i−dp[i−1]−2]。

最后的答案即为 dp 数组中的最大值。

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function(s) {
    let maxans = 0;
    let dp = new Array (s.length).fill(0);
    for (let i = 1; i < s.length; i++) {
        if (s[i] === ')') {
            if (s[i - 1] === '(') {
                dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
            } else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] === '(') {
                dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
            }
            maxans = Math.max(maxans, dp[i]);
        }
    }
    return maxans;
};

使用栈存储上一个开始的位置以来所有的(位置符号

具体做法是我们始终保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」，这样的做法主要是考虑了边界条件的处理，栈里其他元素维护左括号的下标：

对于遇到的每个 ‘(’ ，我们将它的下标放入栈中
对于遇到的每个‘)’ ，我们先弹出栈顶元素表示匹配了当前右括号：
如果栈为空，说明当前的右括号为没有被匹配的右括号，我们将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」
如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」
我们从前往后遍历字符串并更新答案即可。

需要注意的是，如果一开始栈为空，第一个字符为左括号的时候我们会将其放入栈中，这样就不满足提及的「最后一个没有被匹配的右括号的下标」，为了保持统一，我们在一开始的时候往栈中放入一个值为 -1 的初始元素。

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function(s) {
    let maxLen = 0;
    let stack = [-1]; 
    for (let i in s) {
        if (s[i] === '(') {
            stack.push(i);
        } else {
            stack.pop();
            if (stack.length > 0) {
                maxLen = Math.max(maxLen, i - stack[stack.length - 1]);
            } else {
                stack.push(i);
            }
        }
    }
    return maxLen;
};

不需要额外的空间
思路和算法

在此方法中，我们利用两个计数器 left 和 right 。首先，我们从左到右遍历字符串，对于遇到的每个 ‘(’，我们增加 left 计数器，对于遇到的每个 ‘)’ ，我们增加 right 计数器。每当 left 计数器与 right 计数器相等时，我们计算当前有效字符串的长度，并且记录目前为止找到的最长子字符串。当 right 计数器比 left 计数器大时，我们将 left 和 right 计数器同时变回 0。

这样的做法贪心地考虑了以当前字符下标结尾的有效括号长度，每次当右括号数量多于左括号数量的时候之前的字符我们都扔掉不再考虑，重新从下一个字符开始计算，但这样会漏掉一种情况，就是遍历的时候左括号的数量始终大于右括号的数量，即 (() ，这种时候最长有效括号是求不出来的。

解决的方法也很简单，我们只需要从右往左遍历用类似的方法计算即可，只是这个时候判断条件反了过来：

当 left 计数器比 right 计数器大时，我们将 left 和 right 计数器同时变回 0
当 left 计数器与 right 计数器相等时，我们计算当前有效字符串的长度，并且记录目前为止找到的最长子字符串
这样我们就能涵盖所有情况从而求解出答案。

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function(s) {
    let left = 0, right = 0, maxlength = 0;
    for (let i in s) {
        if (s[i] == '(') {
            left++;
        } else {
            right++;
        }
        if (left == right) {
            maxlength = Math.max(maxlength, 2 * right);
        } else if (right > left) {
            left = right = 0;
        }
    }
    left = right = 0;
    for (let i = s.length - 1; i >= 0; i--) {
        if (s.charAt(i) == '(') {
            left++;
        } else {
            right++;
        }
        if (left == right) {
            maxlength = Math.max(maxlength, 2 * left);
        } else if (left > right) {
            left = right = 0;
        }
    }
    return maxlength;
};

62. 不同路径

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

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

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

示例 1：

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

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

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

示例 4：

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

提示：

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

使用动态规划，dp[i][j]表示到第i+1行第j+1列有多少种方法

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function (m, n) {
	let dp = new Array(m).fill(1).map(() => new Array(n).fill(1));
	for (let i = 1; i < m; i++) {
		for (let j = 1; j < n; j++) {
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
		}
	}
	return dp[m - 1][n - 1];
};

优化空间，降至1维空间

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function (m, n) {
    if (m < n) return uniquePaths(n, m);
	let dp = new Array(n).fill(1);
	for (let i = 1; i < m; i++) {
		for (let j = 1; j < n; j++) {
			dp[j] = dp[j] + dp[j - 1];
		}
	}
	return dp[n - 1];
};

使用排列组合

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 * 排列组合
 * C(m + n - 2, m - 1)
 */
var uniquePaths = function(m, n) {
    let N = n + m - 2;
    let k = m - 1;
    let result = 1;
    for (let i = 1; i <= k; i++) {
        result = result * (N - k + i) / i;
    }
    return result;
};

64. 最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例 1：

1
2
3

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

1 2	输入：grid = [[1,2,3],[4,5,6]] 输出：12

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100

直接写压缩后的动态规划

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
    if (!grid.length || !grid[0].length) return 0;
    let m = grid.length, n = grid[0].length;
    let currentSum = 0;
    // 第0行的每个点的路径和
    let dp = grid[0].map((value) => {
        currentSum += value;
        return currentSum;
    })
    for (let i = 1; i < m; i++) {
        // 第0列的每个点的路径和
        dp[0] += grid[i][0];
        for (let j = 1; j < n; j++) {
            // 空间压缩
            dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
        }
    }
    return dp[n - 1];
};

72. 编辑距离

给你两个单词 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 由小写英文字母组成

直接比较word1前i个字母到word2前j个字母的编辑距离

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function(word1, word2) {
    let m = word1.length, n = word2.length;
    // 构建 DP table
    let dp = new Array(m + 1);
    // base case
    for (i = 0; i <= m; i++) {
        dp[i] = new Array(n + 1).fill(0);
        dp[i][0] = i;
    }
    for (j = 1; j <= n; j++) {
        dp[0][j] = j;
    }
    // 进行状态转移
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (word1[i - 1] === word2[j - 1]) {
                // 找到一个 lcs 中的字符
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
            }
        }
    }
    // 储存着整个 s1 和 s2 的最小编辑距离
    return dp[m][n];
};

优化空间

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 * 空间压缩
 */
var minDistance = function(word1, word2) {
    let m = word1.length, n = word2.length;
    if (m < n) return minDistance(word2, word1);
    // 构建 DP table
    let dp = new Array(n + 1);
    // base case
    for (j = 0; j <= n; j++) {
        dp[j] = j;
    }
    // 进行状态转移
    for (let i = 1; i <= m; i++) {
        // 保存dp[i - 1][j - 1]
        let pre = dp[0];
        dp[0] = i;
        for (let j = 1; j <= n; j++) {
            let tmp = dp[j];
            // dp[i][j] = Math.min(dp[i - 1][j - 1] + ((word1[i - 1] == word2[j - 1]) ? 0 : 1), Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
            dp[j] = Math.min(pre + ((word1[i - 1] == word2[j - 1]) ? 0 : 1), Math.min(dp[j - 1] + 1, dp[j] + 1));
            pre = tmp;
        }
    }
    return dp[n];
};

139. 单词拆分

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

示例 1：

1
2
3

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。

示例 3：

1 2	输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: false

动态规划中的0-1背包

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function(s, wordDict) {
    // 目标单词的长度
    const target = s.length;
    // dp的意思是目标单词能否被拆分
    const dp = new Array(target + 1).fill(false);
    dp[0] = true;
    // 完全背包和排序问题
    for(let i = 1; i <= target; i++) {
        for (let j = 0; j < wordDict.length; j++) {
            // 遍历每个单词，判断当前目标单词的最后几个词汇能够被拆分
            const len = wordDict[j].length;
            if (i >= len && wordDict[j] === s.slice(i - len, i)) {
                dp[i] = dp[i] || dp[i - len];
            }
        }
    }
    return dp[target];
};

152. 乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

示例 1:

1
2
3

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

示例 2:

1
2
3

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

其实就是把最大子序和同时考虑最小积和最大积，以实现同时兼顾正数和负数

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function(nums) {
    let max = nums[0];
    let imax = 1;
    let imin = 1;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] < 0) {
            let temp = imax;
            imax = imin;
            imin = temp;
        }
        imax = Math.max(nums[i], nums[i] * imax);
        imin = Math.min(nums[i], nums[i] * imin);
        max = Math.max(imax, max);        
    }
    return max;
};

198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 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

对于每个点选择偷或不偷，分别计算最大值

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    if (!nums || !nums.length) return 0;
    let dp0 = 0, dp1 = 0;
    for (let i = 0; i < nums.length; i++) {
        let dp_temp = Math.max(dp0 + nums[i], dp1);
        // 不抢第i个房间的最大值
        dp0 = dp1;
        // 第i个房间的抢到的最大值
        dp1 = dp_temp;
    }
    return dp1;
};

221. 最大正方形

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

示例 1：

1 2	输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] 输出：4

示例 2：

1 2	输入：matrix = [["0","1"],["1","0"]] 输出：1

示例 3：

1 2	输入：matrix = [["0"]] 输出：0

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] 为 ‘0’ 或 ‘1’

dp[i][j]代表以(i, j)为右下角的最大正方形边长

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalSquare = function(matrix) {
    // dp[i][j]代表以(i, j)为右下角的最大正方形边长
    let dp = [];
    let max = 0;
    for (let i = 0; i < matrix.length; i++) {
        dp[i] = [];
        for (let j = 0; j < matrix[0].length; j++){
            if (matrix[i][j] === 0){
                dp[i][j] = 0;
            } else if (i === 0 || j === 0){
                dp[i][j] = 1;
            } else {
                dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;
            }
            if(dp[i][j] > max){
                max = dp[i][j];
            }
        }
    }
    return max * max;
};

压缩空间

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalSquare = function(matrix) {
    // dp[j]代表以(i, j)为右下角的最大正方形边长
    let m = matrix.length;
    if (!m) return 0;
    let n = matrix[0].length;
    if (!n) return 0;
    let dp = [];
    let max = 0;
    for (let j = 0; j < n; j++) {
        dp[j] = matrix[0][j];
        max |= dp[j];
    }
    for (let i = 1; i < m; i++){
        let temp = dp[0];
        dp[0] = matrix[i][0];
        if (dp[0] > max) {
            max = dp[0];
        }
        for (let j = 1; j < matrix[0].length; j++){
            // 压缩路径
            let pre = temp;
            temp = dp[j];
            if (matrix[i][j] === 0){
                dp[j] = 0;
            } else {
                dp[j] = Math.min(pre, dp[j - 1], dp[j]) + 1;
            }
            if(dp[j] > max){
                max = dp[j];
            }
        }
    }
    return max * max;
};

279. 完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。

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

示例 1：

1
2
3

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

示例 2：

1
2
3

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

提示：

1 <= n <= 104

动态规划完全问题的转化，其实就是0-1背包问题

/**
 * @param {number} n
 * @return {number}
 * 动态规划
 */
var numSquares = function(n) {
    let dp = new Array(n + 1).fill(n);
    // base case
    dp[0] = 0;
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j * j <= i; j++) {
            dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
        }
    }
    return dp[n];
};

这么写还不清楚吗

/**
 * @param {number} n
 * @return {number}
 * 动态规划
 */
var numSquares = function(n) {
    // 转换为背包问题
    let sqrt = Math.floor(Math.sqrt(n));
    let coins = [];
    // 硬币为各个完全平方数
    for (let i = 0; i < sqrt; i++) {
        coins[i] = (i + 1) * (i + 1);
    }
    let dp = new Array(n + 1).fill(Infinity);
    // base case
    dp[0] = 0;
    for (let i = 1; i <= n; i++) {
        for (let coin of coins) {
            if (i >= coin) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[n];
};

贪心算法

/**
 * @param {number} n
 * @return {number}
 * 贪心算法
 */
var numSquares = function(n) {
    let count = 1;
    while (count <= n) {
        if (is_divided_by(n, count)) {
            break;
        }
        count++;
    }
    return count;
};

function is_divided_by(sum, count) {    
    const sq = parseInt(Math.sqrt(sum));
    if (count === 1) return sq * sq === sum;
    for (let num = sq; num >= 1; num--) {
        if (is_divided_by(sum - num * num, count - 1)) {
            return true;
        }
    }
    return false;
}

数学方法

一个数学定理可以帮助解决本题：「四平方和定理」。

四平方和定理证明了任意一个正整数都可以被表示为至多四个正整数的平方和。这给出了本题的答案的上界。

同时四平方和定理包含了一个更强的结论：当且仅当 $$n \neq 4^k \times (8m+7)$$时，$$n$$ 可以被表示为至多三个正整数的平方和。因此，当 $$n = 4^k \times (8m+7)$$ 时，$$n$$ 只能被表示为四个正整数的平方和。此时我们可以直接返回 $$4$$。

当 $$n \neq 4^k \times (8m+7)$$ 时，我们需要判断到底多少个完全平方数能够表示 $$n$$，我们知道答案只会是 $$1,2,3$$ 中的一个：

答案为 $$1$$ 时，则必有 $$n$$ 为完全平方数，这很好判断；
答案为 $$2$$ 时，则有 $$n=a^2+b^2$$ ，我们只需要枚举所有的 $$a(1 \leq a \leq \sqrt{n})$$，判断 $$n-a^2$$ 是否为完全平方数即可；
答案为 $$3$$ 时，我们很难在一个优秀的时间复杂度内解决它，但我们只需要检查答案为 $$1$$ 或 $$2$$ 的两种情况，即可利用排除法确定答案。

/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function (n) {
    // 处理1个数的情况
    let pow = Math.sqrt(n);
    if(pow >> 0 === pow) return 1;

    // 处理2个数的情况
    for(let i = 1; i * i <= n; i++) {
        let ans = n - i * i;
        let pow = Math.sqrt(ans);
        if(pow >> 0 === pow) return 2;
    }

    // 处理4个数的情况
    let m = n;
    while(m % 4 === 0) m = m / 4;
    if(m % 8 === 7) return 4;
    // 剩下3个数的情况
    return 3;
};

300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

1
2
3

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

1 2	输入：nums = [0,1,0,3,2,3] 输出：4

示例 3：

1 2	输入：nums = [7,7,7,7,7,7,7] 输出：1

提示：

1 <= nums.length <= 2500
-104 <= nums[i] <= 104

进阶：

你可以设计时间复杂度为 O(n2) 的解决方案吗？
你能将算法的时间复杂度降低到 O(n log(n)) 吗?

动态规划较为简单

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
    let n = nums.length;
    if (n === 0) return 0;
    // base case：dp 数组全都初始化为 1
    // dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度
    let dp = new Array(n).fill(1);
    let res = 0;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        res = Math.max(dp[i], res);
    }
    return res;
};

动态规划 + 二分查找
解题思路：
降低复杂度切入点：解法一中，遍历计算 dp 列表需 O(N)，计算每个 dp[k]需 O(N)。

动态规划中，通过线性遍历来计算 dp 的复杂度无法降低；
每轮计算中，需要通过线性遍历 [0,k) 区间元素来得到 dp[k] 。我们考虑：是否可以通过重新设计状态定义，使整个 dp 为一个排序列表；这样在计算每个 dp[k] 时，就可以通过二分法遍历 [0,k) 区间元素，将此部分复杂度由 O(N) 降至 O(logN)。
设计思路：

新的状态定义：
我们考虑维护一个列表 tails，其中每个元素 tails[k] 的值代表长度为 k+1 的子序列尾部元素的值。
如 [1,4,6] 序列，长度为 1,2,3 的子序列尾部元素值分别为 tails = [1,4,6]。
状态转移设计：
设常量数字 N，和随机数字 x，我们可以容易推出：当 N 越小时，N<x 的几率越大。例如： N=0 肯定比 N=1000 更可能满足 N<x。
在遍历计算每个 tails[k]，不断更新长度为 [1,k] 的子序列尾部元素值，始终保持每个尾部元素值最小（例如 [1,5,3]，遍历到元素 5 时，长度为 2 的子序列尾部元素值为 5；当遍历到元素 3 时，尾部元素值应更新至 3，因为 3 遇到比它大的数字的几率更大）。
tails 列表一定是严格递增的：即当尽可能使每个子序列尾部元素值最小的前提下，子序列越长，其序列尾部元素值一定更大。
反证法证明：当 k < i，若 tails[k] >= tails[i]，代表较短子序列的尾部元素的值 > 较长子序列的尾部元素的值。这是不可能的，因为从长度为 ii 的子序列尾部倒序删除 i-1 个元素，剩下的为长度为 k 的子序列，设此序列尾部元素值为 v，则一定有 v<tails[i] （即长度为 k 的子序列尾部元素值一定更小），这和 tails[k] >= tails[i] 矛盾。
既然严格递增，每轮计算 tails[k] 时就可以使用二分法查找需要更新的尾部元素值的对应索引 i。
算法流程：

状态定义：

tails[k] 的值代表长度为 k+1 子序列的尾部元素值。
转移方程：设 res 为 tails 当前长度，代表直到当前的最长上升子序列长度。设 j∈[0, res)，考虑每轮遍历 nums[k] 时，通过二分法遍历 [0, res) 列表区间，找出 nums[k] 的大小分界点，会出现两种情况：

区间中存在 tails[i] > nums[k] ：将第一个满足 tails[i] > nums[k] 执行 tails[i] = nums[k] ；因为更小的 nums[k] 后更可能接一个比它大的数字（前面分析过）。
区间中不存在 tails[i] > nums[k] ：意味着 nums[k] 可以接在前面所有长度的子序列之后，因此肯定是接到最长的后面（长度为 res ），新子序列长度为 res + 1。
初始状态：

令 tails 列表所有值 =0。
返回值：

返回 res ，即最长上升子子序列长度。
复杂度分析：
时间复杂度 O(NlogN) ：遍历 nums 列表需 O(N)，在每个 nums[i] 二分法需 O(logN)。
空间复杂度 O(N) ： tails 列表占用线性大小额外空间。

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
    let n = nums.length;
    if (n == 0) return 0;
    let dp = [];
    // 辅助序列
    dp[0] = nums[0];
    for (let i = 1; i < n; i++) {
        if (nums[i] > dp[dp.length - 1]) {
            dp.push(nums[i]);
        } else {
            let left = 0, right = dp.length - 1;
            // 二分查找
            while (left < right) {
                let mid = (left + right) >> 1;
                if (dp[mid] < nums[i]) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            dp[left] = nums[i];
        }
    }
    return dp.length;
}

309. 最佳买卖股票时机含冷冻期

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

示例:

1
2
3

输入: [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

请问您在哪类招聘中遇到此题？

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    // 第一次 买入，卖出的利润
    let dp_i_0 = 0, dp_i_1 = Number.MIN_SAFE_INTEGER;
    // 第二次 买入，卖出的利润
    let dp_pre_0 = 0; // 代表 dp[i-2][0]
    for (let price of prices) {
        let temp = dp_i_0;
        // dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
        dp_i_0 = Math.max(dp_i_0, dp_i_1 + price);
        // dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])
        dp_i_1 = Math.max(dp_i_1, dp_pre_0 - price);
        dp_pre_0 = temp;
    }
    return dp_i_0;
};

312. 戳气球

有 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 =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167

示例 2：

1 2	输入：nums = [1,5] 输出：10

提示：

n == nums.length
1 <= n <= 500
0 <= nums[i] <= 100

子问题的划分：

对于区间(i, j), k为[i+1, j-1]中的一个项，以k为中点，把(i, j)划分为(i, k)和（k, j)。

因为子问题(i, k),(k, j)都是不包括边界i,k,j，所以子问题(i, k),(k, j)是相互独立的。

dp数组的定义：dp[i][j]为（i, j）区间所能获得的最大硬币

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxCoins = function(nums) {
    let n = nums.length;
    // 添加两侧的虚拟气球
    let point = [1, ...nums, 1];
    // base case 已经都被初始化为 0 dp[i][j] = x 表示，戳破气球 i 和气球 j 之间（开区间，不包括 i 和 j）的所有气球，可以获得的最高分数为 x
    let dp = new Array(n + 2);
    for (let i = 0; i <= n + 1; i++) {
        dp[i] = new Array(n + 2).fill(0);
    }
    // 开始状态转移
    // i 应该从下往上
    for (let i = n; i >= 0; i--) {
        // j 应该从左往右
        for (let j = i + 1; j < n + 2; j++) {
            // 最后戳破的气球是哪个？
            for (let k = i + 1; k < j; k++) {
                // 择优做选择
                dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + point[i] * point[j] * point[k]);
            }
        }
    }
    return dp[0][n + 1];
};

322. 零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

示例 1：

1
2
3

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

1 2	输入：coins = [2], amount = 3 输出：-1

示例 3：

1 2	输入：coins = [1], amount = 0 输出：0

示例 4：

1 2	输入：coins = [1], amount = 1 输出：1

示例 5：

1 2	输入：coins = [1], amount = 2 输出：2

提示：

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

dp[i]表示总金额为i元的方法

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
    // 压缩路径
    // 数组大小为 amount + 1
    let dp = new Array(amount + 1).fill(Infinity);
    // base case
    dp[0] = 0;
    // 外层 for 循环在遍历所有状态的所有取值
    for (let i = 1; i <= amount; i++) {
        // 内层 for 循环在求所有选择的最小值
        for (let coin of coins) {
            if (i - coin < 0) continue;
            dp[i] = Math.min(dp[i], dp[i - coin] + 1);
        }
    }
    return dp[amount] === Infinity ? -1: dp[amount];
};

337. 打家劫舍 III

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例 1:

输入: [3,2,3,null,3,null,1]

     3
    / \
   2   3
    \   \ 
     3   1

输出: 7 
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

示例 2:

输入: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \ 
 1   3   1

输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

动态规划结合二叉树DFS

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var rob = function(root) {
    let res = dp(root);
    return Math.max(res[0], res[1]);
};

/* 返回一个大小为 2 的数组 arr
arr[0] 表示不抢 root 的话，得到的最大钱数
arr[1] 表示抢 root 的话，得到的最大钱数 */
function dp(root) {
    if (!root) return [0, 0];
    let left = dp(root.left);
    let right = dp(root.right);
    // 抢，下家就不能抢了
    let rob = root.val + left[0] + right[0];
    let not_rob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    return [not_rob, rob];
}

使用哈希保存路径

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var rob = function (root) {
    const hash = new Map();

    return helper(root, hash);
}

function helper(root, hash) {
    if (!root) return 0;
    if (hash.has(root)) return hash.get(root);

    let money = root.val;

    if (root.left) money += (helper(root.left.left, hash) + helper(root.left.right, hash));
    if (root.right) money += (helper(root.right.left, hash) + helper(root.right.right, hash));

    const res = Math.max(money, helper(root.left, hash) + helper(root.right, hash));
    hash.set(root, res);
    return res;
}

416. 分割等和子集

给你一个 只包含正整数 的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

1
2
3

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

1
2
3

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

提示：

1 <= nums.length <= 200
1 <= nums[i] <= 100

dp[i][j] 表示用前i个数能够组成和为j

/**
 * @param {number[]} nums
 * @return {boolean}
 * 动态规划
 */
var canPartition = function(nums) {
    let sum = nums.reduce((a, b) => a + b);
    if (sum % 2 === 1) return false;
    let n = nums.length;
    sum = sum / 2;
    dp = new Array(n + 1);
    // dp[i][j] 表示用前i个数能够组成和为j
    for (let i = 0; i <= n; i++) {
        dp[i] = Array(sum + 1).fill(false);
        // base case
        dp[i][0] = true;
    }
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= sum; j++) {
            if (j >= nums[i - 1]) {
                // 可以选择装入或不装入背包
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
            } else {
                // 无法将第i-1个数装入背包
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[n][sum];
};

可以优化空间

/**
 * @param {number[]} nums
 * @return {boolean}
 * 优化空间后的方案
 */
var canPartition = function(nums) {
    let sum = nums.reduce((a, b) => a + b);
    if (sum % 2) return false;
    let n = nums.length;
    sum = sum / 2;
    dp = new Array(sum + 1).fill(false);
    dp[0] = true;
    for (let i = 1; i <= n; i++) {
        for (let j = sum; j >= 1; j--) {
            if (j - nums[i - 1] >= 0) {
                // 装入或不装入背包
                dp[j] = dp[j] || dp[j - nums[i - 1]];
            }
        }
    }
    return dp[sum];
};

进一步简化

/**
 * @param {number[]} nums
 * @return {boolean}
 * 优化空间后的方案
 */
var canPartition = function(nums) {
    let sum = nums.reduce((a, b) => a + b);
    if (sum % 2) return false;
    let n = nums.length;
    sum = sum / 2;
    dp = new Array(sum + 1).fill(false);
    dp[0] = true;
    for (let i = 1; i <= n; i++) {
        for (let j = sum; j >= nums[i - 1]; j--) {
            // 装入或不装入背包
            dp[j] = dp[j] || dp[j - nums[i - 1]];
        }
    }
    return dp[sum];
};

474. 一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的大小，该子集中最多有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的子集。

示例 1：

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：

1
2
3

输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。

提示：

1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] 仅由 '0' 和 '1' 组成
1 <= m, n <= 100

和0-1背包问题类似的做法，外层循环遍历背包里的数，内层循环从大到小遍历可能的值，实现动态规划数组最小值并压缩路径

/**
 * @param {string[]} strs
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var findMaxForm = function(strs, m, n) {
    // dp(i, j) 表示使用 i 个 0 和 j 个 1，最多能拼出的字符串数目 状态压缩至二维
    let dp = Array.from(new Array(m + 1), () => new Array(n + 1).fill(0));
    for (let str of strs) {
        let [count0, count1] = count(str);
        for (let i = m; i >= count0; i--) {
            for (let j = n; j >= count1; j--) {
                dp[i][j] = Math.max(dp[i][j], 1 + dp[i - count0][j - count1]);
            }
        }
    }
    return dp[m][n];
};

// 辅函数
function count(s){
    let count0 = s.length, count1 = 0;
    for (let c of s) {
        if (c === 1) {
            count1++;
            count0--;
        }
    }
    return [count0, count1];
}

494. 目标和

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

示例 2：

1 2	输入：nums = [1], target = 1 输出：1

提示：

1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000

dp[i][j]表示用了前i个数实现和为j的方法数

/**
 * @param {number[]} nums
 * @param {number} S
 * @return {number}
 */
var findTargetSumWays = function(nums, S) {
    if (nums.length == 0) return S == 0;
    let sum = nums.reduce((prev, next) => prev + next, 0);
    if (Math.abs(sum) < Math.abs(S)) return 0;
    let dp = new Array(nums.length);
    for (let i = 0; i < nums.length; i++) {
        dp[i] = new Array(sum * 2 + 1).fill(0);
    }
    if (nums[0] === 0) {
        dp[0][sum] = 2;
    } else {
        dp[0][sum + nums[0]] = 1;
        dp[0][sum - nums[0]] = 1;
    }
    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j <= 2 * sum; j++) {
            let l = (j - nums[i]) >= 0 ? j - nums[i]: 0;
            let r = (j + nums[i]) <= 2 * sum ? j + nums[i]: 0;
            dp[i][j] = dp[i - 1][l] + dp[i - 1][r];
        }
    }
    return dp[nums.length - 1][sum + S];
};

空间优化方案

/**
 * @param {number[]} nums
 * @param {number} S
 * @return {number}
 */
var findTargetSumWays = function(nums, S) {
    let sum = nums.reduce((a, b) => a + b);
    // 这句千千万万要考虑到~
    if(S > sum || S < -sum) return 0;
    let total = sum - S;
    // 奇偶性判断
    if((total & 1) === 1) return 0;
    // 部分和为n
    let n = total / 2;
    let dp = new Array(n + 1).fill(0);
    dp[0] = 1;
    for (let i = 0; i < nums.length; i++) {
        // 反着遍历不影响结果
       for (let j = n; j >= nums[i]; j--) {
            dp[j] += dp[j - nums[i]];
       }
    }
    return dp[n];
};

518. 零钱兑换 II

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例 1：

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2：

1
2
3

输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。

示例 3：

1 2	输入：amount = 10, coins = [10] 输出：1

提示：

1 <= coins.length <= 300
1 <= coins[i] <= 5000
coins 中的所有值 互不相同
0 <= amount <= 5000

dp[i][j]表示使用前i种货币达到j元的方法数

/**
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
var change = function(amount, coins) {
    let n = coins.length;
    let dp = new Array(n + 1);
    // base case
    for (let i = 0; i <= n; i++) {
        dp[i] = new Array(amount + 1).fill(0);
        dp[i][0] = 1;
    }
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= amount; j++) {
            if (j - coins[i - 1] >= 0) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]];
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[n][amount];
};

优化为一维动态规划数组

/**
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
var change = function(amount, coins) {
    let dp = new Array(amount + 1).fill(0);
    dp[0] = 1;
    for (let coin of coins) {
        for (let i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }
    return dp[amount];
};

664. 奇怪的打印机

有台奇怪的打印机有以下两个特殊要求：

打印机每次只能打印由 同一个字符 组成的序列。
每次可以在任意起始和结束位置打印新字符，并且会覆盖掉原来已有的字符。

给你一个字符串 s ，你的任务是计算这个打印机打印它需要的最少打印次数。

示例 1：

1
2
3

输入：s = "aaabbb"
输出：2
解释：首先打印 "aaa" 然后打印 "bbb"。

示例 2：

1
2
3

输入：s = "aba"
输出：2
解释：首先打印 "aaa" 然后在第二个位置打印 "b" 覆盖掉原来的字符 'a'。

提示：

1 <= s.length <= 100
s 由小写英文字母组成

万事不决动态规划，这种一看就知道需要二维数组，重点是需要三轮循环找到最小值，有点类似戳气球

/**
 * @param {string} s
 * @return {number}
 * 动态规划
 */
var strangePrinter = function(s) {
    // 长度
    const n = s.length;
    // dp[i][j]表示i位置开头到j位置所需的最小打印次数
    let dp = Array.from(new Array(n), () => new Array(n).fill(0));
    // 开头位置从后往前计算
    for (let i = n - 1; i >= 0; i--) {
        // base case
        dp[i][i] = 1;
        // dp[i][j]计算需要借助dp[i][k](i<k<j)
        for (let j = i + 1; j < n; j++) {
            if (s[i] === s[j]) {
                 // 首尾相同，无需循环，与dp[i][j - 1]一样的次数
                dp[i][j] = dp[i][j - 1];
            } else {
                // 最小的和
                let min = Number.MAX_SAFE_INTEGER;
                for (let k = i; k < j; k++) {
                    // 两个区间打印次数的和
                    min = Math.min(dp[i][k] + dp[k + 1][j], min);
                }
                // 最小的结果
                dp[i][j] = min;
            }
        }
    }
    return dp[0][n - 1];
};

879. 盈利计划

集团里有 n 名员工，他们可以完成各种各样的工作创造利润。

第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与。如果成员参与了其中一项工作，就不能参与另一项工作。

工作的任何至少产生 minProfit 利润的子集称为 盈利计划 。并且工作的成员总数最多为 n 。

有多少种计划可以选择？因为答案很大，所以 返回结果模 10^9 + 7 的值。

示例 1：

输入：n = 5, minProfit = 3, group = [2,2], profit = [2,3]
输出：2
解释：至少产生 3 的利润，该集团可以完成工作 0 和工作 1 ，或仅完成工作 1 。
总的来说，有两种计划。

示例 2：

输入：n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
输出：7
解释：至少产生 5 的利润，只要完成其中一种工作就行，所以该集团可以完成任何工作。
有 7 种可能的计划：(0)，(1)，(2)，(0,1)，(0,2)，(1,2)，以及 (0,1,2) 。

提示：

1 <= n <= 100
0 <= minProfit <= 100
1 <= group.length <= 100
1 <= group[i] <= 100
profit.length == group.length
0 <= profit[i] <= 100

需要用到三维数组，三重循环展开

/**
 * @param {number} n
 * @param {number} minProfit
 * @param {number[]} group
 * @param {number[]} profit
 * @return {number}
 */
var profitableSchemes = function(n, minProfit, group, profit) {
    // 长度为工作数量
    const len = group.length, MOD = 1e9 + 7;
    // dp[i][j][k] 表示在进行前 i 种工作，使用恰好 j 个人，工作利润至少为 k 的情况数量
    const dp = new Array(len + 1).fill(0).map(() => new Array(n + 1).fill(0).map(() => new Array(minProfit + 1).fill(0)));
    // base case
    dp[0][0][0] = 1;
    // 便利
    for (let i = 1; i <= len; i++) {
        const members = group[i - 1], earn = profit[i - 1];
        for (let j = 0; j <= n; j++) {
            for (let k = 0; k <= minProfit; k++) {
                if (j < members) {
                    // 无法开展当前工作 i
                    dp[i][j][k] = dp[i - 1][j][k];
                } else {
                    // 能够开展当前工作
                    dp[i][j][k] = (dp[i - 1][j][k] + dp[i - 1][j - members][Math.max(0, k - earn)]) % MOD;
                }
            }
        }
    }
    let sum = 0;
    for (let j = 0; j <= n; j++) {
        sum = (sum + dp[len][j][minProfit]) % MOD;
    }
    return sum;
};

优化成二维数组

/**
 * @param {number} n
 * @param {number} minProfit
 * @param {number[]} group
 * @param {number[]} profit
 * @return {number}
 * 降为二维
 */
var profitableSchemes = function(n, minProfit, group, profit) {
    const m = profit.length, MOD = 1e9 + 7;
    // dp[i][k]为刚好使用 i 个人，利润大于等于 k 的方案数
    const dp = new Array(n + 1).fill(0).map(() => new Array(minProfit + 1).fill(0));
    // base case
    dp[0][0] = 1;
    // 遍历
    for (let j = 1; j <= m; j++) {
        for (let i = n; i >= group[j - 1]; i--) {
            for (let k = minProfit; k >= 0; k--) {
                dp[i][k] = (dp[i][k] + dp[i - group[j - 1]][Math.max(0, k - profit[j - 1])]) % MOD;
            }
        }
    }
    let sum = 0;
    for (let i = 0; i <= n; i++) {
        sum = (sum + dp[i][minProfit]) % MOD;
    }
    return sum;
};

1049. 最后一块石头的重量 II

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

示例 1：

输入：stones = [2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

示例 2：

1 2	输入：stones = [31,26,33,21,40] 输出：5

示例 3：

1 2	输入：stones = [1,2] 输出：1

提示：

1 <= stones.length <= 30
1 <= stones[i] <= 100

本质上就是变种的部分和是总和一半的0-1背包问题

/**
 * @param {number[]} stones
 * @return {number}
 * 0-1背包问题
 */
var lastStoneWeightII = function(stones) {
    // 和
    const sum = stones.reduce((a, b) => a + b);
    const n = stones.length, m = Math.floor(sum / 2);
    // dp[i][j] 表示在数组 nums 的前 i 个数中选取元素，使得这些元素之和等于 j 的方案数
    const dp = new Array(n + 1).fill(0).map(() => new Array(m + 1).fill(false));
    // base case
    dp[0][0] = true;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j <= m; j++) {
            // 状态转移
            if (j < stones[i]) {
                dp[i + 1][j] = dp[i][j];
            } else {
                dp[i + 1][j] = dp[i][j] || dp[i][j - stones[i]];
            }
        }
    }
    for (let j = m;; j--) {
        if (dp[n][j]) {
            return sum - 2 * j;
        }
    }
};

优化一下空间

/**
 * @param {number[]} stones
 * @return {number}
 * 0-1背包问题
 * 优化
 */
var lastStoneWeightII = function(stones) {
    // 和
    const sum = stones.reduce((a, b) => a + b);
    const n = stones.length, m = Math.floor(sum / 2);
    // dp[i][j] 表示在数组 nums 的前 i 个数中选取元素，使得这些元素之和等于 j 的方案数
    // const dp = new Array(n + 1).fill(0).map(() => new Array(m + 1).fill(false));
    const dp = new Array(m + 1).fill(false);
    // base case
    // dp[0][0] = true;
    dp[0] = true;
    // for (let i = 0; i < n; i++) {
    //     for (let j = 0; j <= m; j++) {
    //         // 状态转移
    //         if (j < stones[i]) {
    //             dp[i + 1][j] = dp[i][j];
    //         } else {
    //             dp[i + 1][j] = dp[i][j] || dp[i][j - stones[i]];
    //         }
    //     }
    // }
    for (const weight of stones) {
        for (let j = m; j >= weight; j--) {
            dp[j] = dp[j] || dp[j - weight];
        }
    }
    for (let j = m;; j--) {
        if (dp[j]) {
        // if (dp[n][j]) {
            return sum - 2 * j;
        }
    }
};

1269. 停在原地的方案数

有一个长度为 arrLen 的数组，开始有一个指针在索引 0 处。

每一步操作中，你可以将指针向左或向右移动 1 步，或者停在原地（指针不能被移动到数组范围外）。

给你两个整数 steps 和 arrLen ，请你计算并返回：在恰好执行 steps 次操作以后，指针仍然指向索引 0 处的方案数。

由于答案可能会很大，请返回方案数模 10^9 + 7 后的结果。

示例 1：

输入：steps = 3, arrLen = 2
输出：4
解释：3 步后，总共有 4 种不同的方法可以停在索引 0 处。
向右，向左，不动
不动，向右，向左
向右，不动，向左
不动，不动，不动

示例 2：

输入：steps = 2, arrLen = 4
输出：2
解释：2 步后，总共有 2 种不同的方法可以停在索引 0 处。
向右，向左
不动，不动

示例 3：

1 2	输入：steps = 4, arrLen = 2 输出：8

提示：

1 <= steps <= 500
1 <= arrLen <= 10^6

这不就是动态规划吗，做了一版发现错了

/**
 * @param {number} steps
 * @param {number} arrLen
 * @return {number}
 */
var numWays = function(steps, arrLen) {
    // 初始化
    let dp = new Array(arrLen).fill(0);
    dp[0] = 1;
    for (let i = 0; i < steps; i++) {
        let pre = 0;
        for (let j = 0; j < arrLen; j++) {
            let temp = dp[j];
            dp[j] = (pre + dp[j] + (j < arrLen - 1 ? dp[j + 1]: 0)) % 1000000007;
            pre = temp;
        }
    }
    return dp[0];
};

未通过的case是434 291270

为什么没通过呢，steps是最长步骤434，最远走不到第434/2个数，而数组过大，后面的数注定为0，却还要参与计算，经过一番改进，终于通过了

/**
 * @param {number} steps
 * @param {number} arrLen
 * @return {number}
 */
var numWays = function(steps, arrLen) {
    // 限制最长的路径
    let m = Math.min((steps >> 1) + 1, arrLen);
    // 初始化
    let dp = new Array(m).fill(0);
    dp[0] = 1;
    for (let i = 0; i < steps; i++) {
        let pre = 0;
        for (let j = 0; j < m; j++) {
            let temp = dp[j];
            dp[j] = (pre + dp[j] + (j < m - 1 ? dp[j + 1]: 0)) % 1000000007;
            pre = temp;
        }
    }
    return dp[0];
};

1449. 数位成本和为目标值的最大数字

给你一个整数数组 cost 和一个整数 target 。请你返回满足如下规则可以得到的最大整数：

给当前结果添加一个数位（i + 1）的成本为 cost[i] （cost 数组下标从 0 开始）。
总成本必须恰好等于 target 。
添加的数位中没有数字 0 。

由于答案可能会很大，请你以字符串形式返回。

如果按照上述要求无法得到任何整数，请你返回 “0” 。

示例 1：

输入：cost = [4,3,2,5,6,7,2,5,5], target = 9
输出："7772"
解释：添加数位 '7' 的成本为 2 ，添加数位 '2' 的成本为 3 。所以 "7772" 的代价为 2*3+ 3*1 = 9 。 "977" 也是满足要求的数字，但 "7772" 是较大的数字。
 数字     成本
  1  ->   4
  2  ->   3
  3  ->   2
  4  ->   5
  5  ->   6
  6  ->   7
  7  ->   2
  8  ->   5
  9  ->   5

示例 2：

1
2
3

输入：cost = [7,6,5,5,5,6,8,7,8], target = 12
输出："85"
解释：添加数位 '8' 的成本是 7 ，添加数位 '5' 的成本是 5 。"85" 的成本为 7 + 5 = 12 。

示例 3：

1
2
3

输入：cost = [2,4,6,2,4,6,4,4,4], target = 5
输出："0"
解释：总成本是 target 的条件下，无法生成任何整数。

示例 4：

1 2	输入：cost = [6,10,15,40,40,40,40,40,40], target = 47 输出："32211"

提示：

cost.length == 9
1 <= cost[i] <= 5000
1 <= target <= 5000

原本的方案在注释里，通过新建一个路径保存参数，打印路径，优化降低空间复杂度，通过计算动态数组的变化判断最优路径

/**
 * @param {number[]} cost
 * @param {number} target
 * @return {string}
 * 动态规划 优化
 */
var largestNumber = function(cost, target) {
    // dp[i+1][j] 表示使用前 i 个数位且花费总成本恰好为 j 时的最大位数
    // const dp = new Array(10).fill(0).map(() => new Array(target + 1).fill(-Number.MAX_VALUE));
    // 优化成为一维数组
    const dp =new Array(target + 1).fill(-Number.MAX_VALUE);
    // 优化掉from数组
    // 二维数组from，在状态转移时记录转移来源
    // const from = new Array(10).fill(0).map(() => new Array(target + 1).fill(0));
    // base case
    // dp[0][0] = 0;
    dp[0] = 0;
    // for (let i = 0; i < 9; i++) {
    //     // 需要的花费
    //     const c = cost[i];
    //     for (let j = 0; j <= target; j++) {
    //         // 不够花费
    //         if (j < c) {
    //             dp[i + 1][j] = dp[i][j];
    //             from[i + 1][j] = j;
    //         } else {
    //             if (dp[i][j] > dp[i + 1][j - c] + 1) {
    //                 dp[i + 1][j] = dp[i][j];
    //                 from[i + 1][j] = j;
    //             } else {
    //                 dp[i + 1][j] = dp[i + 1][j - c] + 1;
    //                 from[i + 1][j] = j - c;
    //             }
    //         }
    //     }
    // }
    for (const c of cost) {
        for (let j = c; j <= target; j++) {
            dp[j] = Math.max(dp[j], dp[j - c] + 1);
        }
    }
    // 无法实现
    // if (dp[9][target] < 0) return "0";
    if (dp[target] < 0) return "0";
    const sb = [];
    let i = 9, j = target;
    // while (i > 0) {
    //     if (j === from[i][j]) {
    //         --i;
    //     } else {
    //         sb.push(i);
    //         j = from[i][j];
    //     }
    // }
    for (let i = 8, j = target; i >= 0; i--) {
        for (let c = cost[i]; j >= c && dp[j] === dp[j - c] + 1; j -= c) {
            sb.push(String.fromCharCode('1'.charCodeAt() + i));
        }
    }
    return sb.join('');
};