整理了一些 leetcode上面的动态规则相关的题目，这是第二个合集，对于动态规划，转移方程最重要，所以每个题目都给出了转移方程。
v[i]是第i个元素的值。v[i][j]是第i行，第j列元素的值
最长有效括号
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
dp[i]表示第i个元素结尾的有效括号的长度。初始化dp[i]全为0。因为(结尾的一定不是有效的，一定为0。所以只需要更新)结尾的位置即可
if (s.charAt(i) == ')') { if (s.charAt(i - 1) == '(') { dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2; } else if (i - dp[i - 1] > 0 && s.charAt(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]); } 复制代码
这种实战意义不大。因为推导公式不容易想出，也很容易出错，知道可以这样做即可。不是唯一方式，用栈的方式实用性更好。
编辑距离
给定两个单词 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') 复制代码
dp[i][j]word1的前i个字符转成word2的前j个字符需要的最少操作数
let word1 = 'aaa' let word2 = 'abcd' let m = word1.length, n = word2.length let dp = [] //第一列为从空字符串到 word2 的第一个字符 for (let i = 0; i < m+1; i++) { dp[i] = [i] } //第一行为从 word1 的第一个字符到空字符串 for (let j = 0; j < n+1; j++) { dp[0][j] = [j] } //递推从 word1 的第 i 个字符转换到 word2 的第 j 个字符需要的最少步数 for (let i = 1; i < m; i++) { for (let j = 1; j < n; j++) { if (word1[i] == word2[j]) { dp[i][j] = dp[i][j] } else { dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1 } } } 复制代码
交错字符串
给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
示例 1:
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" 输出: true 复制代码
示例 2:
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" 输出: false 复制代码
和编辑距离有点像
dp[i][j]且示s1的前i个字符，s2的前j个字符能否构成s3的前i+j个字符
let s1 = 'aaa' let s2 = 'abcd' let s3 = 'aabcaa' let m = s1.length, n = s2.length //空字符和空字符可以组成空字符 let dp = [[true]] //第一列表示不考虑 s2 ， s1 能否构成 s3 for (let i = 1; i < m; i++) { dp[i] = [s1[i - 1] === s3[i - 1]] } //第一行表示不考虑s1，s2能否构成word3 for (let j = 1; j < n; j++) { dp[0][j] = s2[j - 1] === s3[j - 1] } for (let i = 1; i < m; i++) { for (let j = 1; j < n; j++) { //无论是 s1,s2谁出一个字符都可以，只要这个字符可以构成当前规模下的s3的最后一个字符 dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]) || (dp[i][j - 1] && s2[j - 1] == s3[i + j - 1]); } } 复制代码
买卖股票的最佳时机 III
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [3,3,5,0,0,3,1,4] 输出: 6 解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出， 这笔交易所能获得利润 = 3-0 = 3 。随后，在第 7 天（股票价格 = 1）的时候买入， 在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。 复制代码
示例 2:
输入: [1,2,3,4,5] 输出: 4 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。 复制代码
示例 3:
输入: [7,6,4,3,1] 输出: 0 解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。 复制代码
动态规划其实就是穷举 + 记忆。按这个思路，可以穷举所有状态
/* dp[i][k][0],第i天进行了k次交易后手上有没有股票，此时利润的最大值 共有 n 天,可以交易 p 次 */ //构建三维数组 for (let i = 0; i < n + 1; i++) { dp[i] = [] for (let k = 0; i < p + 1; p++) { dp[i][k] = [] } } //构建 dp[0][k][0] = 0 //第0天相当于交易还没开始，从第1天开始 for (let k = 0; k < p; k++) { //解释：因为 i 是从 1 开始的，所以 i = -1 意味着还没有开始，这时候的利润当然是 0 。 dp[0][k][0] = 0 //解释：还没开始的时候，是不可能持有股票的，用负无穷表示这种不可能。 dp[0][k][1] = -infinity } for (let i = 0; i < n + 1; i++) { //用到这种状态的可能是不可能有利润的。也就排除了这种可能 dp[i][0][0] = 0 //解释：因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0 。 dp[i][0][1] = -infinity //解释：不允许交易的情况下，是不可能持有股票的，用负无穷表示这种不可能。 } //v[i-1]表示第i天的价格 for (let i = 1; i < n + 1; i++) { for (let k = 1; i < p + 1; p++) { dp[i][k][0] = Math.max(dp[i - 1][k][1] + v[i - 1], dp[i - 1][k][0]) dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k][0] - v[i - 1]) } } return dp[i][k][0] 复制代码
停在原地的方案数
有一个长度为 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： 输入：steps = 4, arrLen = 2 输出：8 复制代码
提示：
1 <= steps <= 500 1 <= arrLen <= 10^6 复制代码
var numWays = function(steps, arrLen) { const MODULO = 1000000007; let maxColumn = Math.min(arrLen - 1, steps); const dp = new Array(steps + 1).fill(0).map(() => new Array(maxColumn + 1).fill(0)); dp[0][0] = 1; for (let i = 1; i <= steps; i++) { for (let j = 0; j <= maxColumn; j++) { dp[i][j] = dp[i - 1][j]; if (j - 1 >= 0) { dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MODULO; } if (j + 1 <= maxColumn) { dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % MODULO; } } } return dp[steps][0]; }; 复制代码
空间上还可以优化，有时间可以自己写一下。
