什么是动静布局
动静布局，英文：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;};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;};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串};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];};63. 不同门路 II（medium）
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右挪动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
当初思考网格中有障碍物。那么从左上角到右下角将会有多少条不同的门路？
网格中的障碍物和空地位别离用 1 和 0 来示意。
示例 1：
输出：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输入：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 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;};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];};64. 最小门路和 (medium)
给定一个蕴含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的门路，使得门路上的数字总和为最小。
阐明：每次只能向下或者向右挪动一步。
示例 1：
输出：grid = [[1,3,1],[1,5,1],[4,2,1]]
输入：7
解释：因为门路 1→3→1→1→1 的总和最小。
示例 2：输出：grid = [[1,2,3],[4,5,6]]
输入：12提醒：
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= gridi <= 100
- 思路：
dp[i][j]示意从矩阵左上角到（i，j）这个网格对应的最小门路和，只有从上到下，从左到右遍历网格，以后最小门路和就是以后的数值加上下面和右边左小的。 - 复杂度：工夫复杂度
O(mn)，m、n别离是矩阵的长和宽。空间复杂度如果原地批改是O(1)，如果新建dp数组就是O(mn)
js：
var minPathSum = function(dp) { let row = dp.length, col = dp[0].length for(let i = 1; i < row; i++)//初始化第一列 dp[i][0] += dp[i - 1][0] for(let j = 1; j < col; j++)//初始化第一行 dp[0][j] += dp[0][j - 1] for(let i = 1; i < row; i++) for(let j = 1; j < col; j++) dp[i][j] += Math.min(dp[i - 1][j], dp[i][j - 1])//取下面和右边最小的 return dp[row - 1][col - 1]};交易股票问题
121. 交易股票的最佳时机（easy）限定交易次数 k=1
122. 交易股票的最佳时机 II（medium）交易次数无限度 k = +infinity
123. 交易股票的最佳时机 III (hrad) 限定交易次数 k=2
188. 交易股票的最佳时机 IV (hard) 限定交易次数 最多次数为 k
309. 最佳交易股票机会含冷冻期(medium) 含有交易冷冻期
714. 交易股票的最佳时机含手续费 (medium) 每次交易含手续费
第5，6道题相当于在第2道题的根底上加了冷冻期和手续费的条件。
限度条件
- 先买入能力卖出
- 不能同时加入多笔交易，再次买入时，须要先卖出
k >= 0能力进行交易，否则没有交易次数
定义操作
- 买入
- 卖出
- 不操作
定义状态
i: 天数k: 交易次数，每次交易蕴含买入和卖出，这里咱们只在买入的时候须要将k - 10: 不持有股票1: 持有股票
举例
dp[i][k][0]//第i天 还能够交易k次 手中没有股票 dp[i][k][1]//第i天 还能够交易k次 手中有股票最终的最大收益是dp[n - 1][k][0]而不是dp[n - 1][k][1]，因为最初一天卖出必定比持有收益更高
状态转移方程
// 明天没有持有股票，分为两种状况：// 1. dp[i - 1][k][0]，昨天没有持有，明天不操作。 // 2. dp[i - 1][k][1] + prices[i] 昨天持有，明天卖出，明天手中就没有股票了。dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])// 明天持有股票，分为两种状况：// 1.dp[i - 1][k][1] 昨天持有，明天不操作// 2.dp[i - 1][k - 1][0] - prices[i] 昨天没有持有，明天买入。dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])//最大利润就是这俩种状况的最大值121. 交易股票的最佳时机（easy）限定交易次数 k=1
给定一个数组 prices ，它的第 i 个元素 prices[i] 示意一支给定股票第 i 天的价格。
你只能抉择 某一天 买入这只股票，并抉择在 将来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你能够从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输出：[7,1,5,3,6,4]
输入：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。留神利润不能是 7-1 = 6, 因为卖出价格须要大于买入价格；同时，你不能在买入前卖出股票。示例 2：
输出：prices = [7,6,4,3,1]
输入：0
解释：在这种状况下, 没有交易实现, 所以最大利润为 0。提醒：
1 <= prices.length <= 105
0 <= prices[i] <= 104
状态转移方程
//第i天不持有 由 第i-1天不持有而后不操作 和 第i-1天持有而后卖出 两种状况的最大值转移过去dp[i][1][0] = Math.max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])//第i天持有 由 第i-1天持有而后不操作 和 第i-1天不持有而后买入 两种状况的最大值转移过去dp[i][1][1] = Math.max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i]) = Math.max(dp[i - 1][1][1], -prices[i]) // k=0时 没有交易次数，dp[i - 1][0][0] = 0k是固定值1，不影响后果，所以能够不必管，简化之后如下
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])dp[i][1] = Math.max(dp[i - 1][1], -prices[i])残缺代码
//工夫复杂度O(n) 空间复杂度O(n)，dp数组第二维是常数const maxProfit = function (prices) { let n = prices.length; let dp = Array.from(new Array(n), () => new Array(2)); dp[0][0] = 0; //第0天不持有 dp[0][1] = -prices[0]; //第0天持有 for (let i = 1; i < n; i++) { dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); dp[i][1] = Math.max(dp[i - 1][1], -prices[i]); } return dp[n - 1][0];};状态压缩，dp[i] 只和 dp[i - 1] 无关，去掉一维
//工夫复杂度O(n) 空间复杂度O(1)const maxProfit = function (prices) { let n = prices.length; let dp = Array.from(new Array(n), () => new Array(2)); dp[0] = 0; dp[1] = -prices[0]; for (let i = 1; i < n; i++) { dp[0] = Math.max(dp[0], dp[1] + prices[i]); dp[1] = Math.max(dp[1], -prices[i]); } return dp[0];};//语意化const maxProfit = function (prices) { let n = prices.length; let sell = 0; let buy = -prices[0]; for (let i = 1; i < n; i++) { sell = Math.max(sell, buy + prices[i]); buy = Math.max(buy, -prices[i]); } return sell;};122. 交易股票的最佳时机 II（medium）交易次数无限度 k = +infinity
给你一个整数数组 prices ，其中 prices[i] 示意某支股票第 i 天的价格。
在每一天，你能够决定是否购买和/或发售股票。你在任何时候 最多 只能持有 一股 股票。你也能够先购买，而后在 同一天 发售。
返回 你能取得的 最大 利润 。
示例 1：
输出：prices = [7,1,5,3,6,4]
输入：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能取得利润 = 5 - 1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能取得利润 = 6 - 3 = 3 。 总利润为 4 + 3 = 7 。示例 2：
输出：prices = [1,2,3,4,5]
输入：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能取得利润 = 5 - 1 = 4 。总利润为 4 。示例 3：
输出：prices = [7,6,4,3,1]
输入：0
解释：在这种状况下, 交易无奈取得正利润，所以不参加交易能够取得最大利润，最大利润为 0 。提醒：
1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104
状态转移方程
//第i天不持有 由 第i-1天不持有而后不操作 和 第i-1天持有而后卖出 两种状况的最大值转移过去dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])//第i天持有 由 第i-1天持有而后不操作 和 第i-1天不持有而后买入 两种状况的最大值转移过去dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])k同样不影响后果，简化之后如下
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i])残缺代码
const maxProfit = function (prices) { let n = prices.length; let dp = Array.from(new Array(n), () => new Array(2)); dp[0][0] = 0; //第0天不持有 dp[0][1] = -prices[0]; //第0天买入 花了prices[0] for (let i = 1; i < n; i++) { dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]); } return dp[n - 1][0];};状态压缩，同样dp[i] 只和 dp[i - 1] 无关，去掉一维
const maxProfit = function (prices) { let n = prices.length; let dp = Array.from(new Array(n), () => new Array(2)); dp[0] = 0; dp[1] = -prices[0]; for (let i = 1; i < n; i++) { dp[0] = Math.max(dp[0], dp[1] + prices[i]); dp[1] = Math.max(dp[1], dp[0] - prices[i]); } return dp[0];};//语意化const maxProfit = function (prices) { let n = prices.length; let sell = 0; let buy = -prices[0]; for (let i = 1; i < n; i++) { sell = Math.max(sell, buy + prices[i]); buy = Math.max(buy, sell - prices[i]); } return sell;};123. 交易股票的最佳时机 III (hrad) 限定交易次数 k=2
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多能够实现 两笔 交易。
留神：你不能同时参加多笔交易（你必须在再次购买前发售掉之前的股票）。
示例 1:
输出：prices = [3,3,5,0,0,3,1,4]
输入：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能取得利润 = 3-0 = 3 。随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能取得利润 = 4-1 = 3 。示例 2：
输出：prices = [1,2,3,4,5]
输入：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能取得利润 = 5-1 = 4 。留神你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。 因为这样属于同时参加了多笔交易，你必须在再次购买前发售掉之前的股票。示例 3：
输出：prices = [7,6,4,3,1]
输入：0
解释：在这个状况下, 没有交易实现, 所以最大利润为 0。
示例 4：输出：prices = [1]
输入：0提醒：
1 <= prices.length <= 105
0 <= prices[i] <= 105
状态转移方程
dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])k对后果有影响 不能舍去，只能对k进行循环
for (let i = 0; i < n; i++) { for (let k = maxK; k >= 1; k--) { dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]); dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]); }}//k=2，间接写出循环的后果dp[i][2][0] = Math.max(dp[i - 1][2][0], dp[i - 1][2][1] + prices[i])dp[i][2][1] = Math.max(dp[i - 1][2][1], dp[i - 1][1][0] - prices[i])dp[i][1][0] = Math.max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])dp[i][1][1] = Math.max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i]) = Math.max(dp[i - 1][1][1], -prices[i])// k=0时 没有交易次数，dp[i - 1][0][0] = 0//去掉i这一维度dp[2][0] = Math.max(dp[2][0], dp[2][1] + prices[i])dp[2][1] = Math.max(dp[2][1], dp[1][0] - prices[i])dp[1][0] = Math.max(dp[1][0], dp[1][1] + prices[i])dp[1][1] = Math.max(dp[1][1], dp[0][0] - prices[i]) = Math.max(dp[1][1], -prices[i])// k=0时 没有交易次数，dp[i - 1][0][0] = 0残缺代码
//和后面一样 咱们间接降维const maxProfit = function (prices) { let buy_1 = -prices[0], sell_1 = 0 let buy_2 = -prices[0], sell_2 = 0 let n = prices.length for (let i = 1; i < n; i++) { sell_2 = Math.max(sell_2, buy_2 + prices[i]) buy_2 = Math.max(buy_2, sell_1 - prices[i]) sell_1 = Math.max(sell_1, buy_1 + prices[i]) buy_1 = Math.max(buy_1, -prices[i]) } return sell_2}188. 交易股票的最佳时机 IV (hard) 限定交易次数 最多次数为 k
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多能够实现 k 笔交易。
留神：你不能同时参加多笔交易（你必须在再次购买前发售掉之前的股票）。
示例 1：
输出：k = 2, prices = [2,4,1]
输入：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能取得利润 = 4-2 = 2 。
示例 2：输出：k = 2, prices = [3,2,6,5,0,3]
输入：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能取得利润 = 6-2 = 4 。随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能取得利润 = 3-0 = 3 。提醒：
0 <= k <= 100
0 <= prices.length <= 1000
0 <= prices[i] <= 1000
const maxProfit = function (k, prices) { let n = prices.length; let profit = new Array(k);//和123题一样 求出所有k的状态 // 初始化k次交易买入卖出的利润 for (let j = 0; j <= k; j++) { profit[j] = { buy: -prices[0],//示意有股票 sell: 0,//示意没有股票 }; } for (let i = 0; i < n; i++) { for (let j = 1; j <= k; j++) { //122题能够交易无数次，188交易k次，所以间接在加一层k循环就能够 //122最初的递推方程： //sell = Math.max(sell, buy + prices[i]); //buy = Math.max(buy, -prices[i]); profit[j] = { sell: Math.max(profit[j].sell, profit[j].buy + prices[i]), buy: Math.max(profit[j].buy, profit[j - 1].sell - prices[i]), }; } } return profit[k].sell; //返回第k次清空手中的股票之后的最大利润};309. 最佳交易股票机会含冷冻期(medium) 含有交易冷冻期
给定一个整数数组prices，其中第 prices[i] 示意第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你能够尽可能地实现更多的交易（屡次交易一支股票）:
卖出股票后，你无奈在第二天买入股票 (即冷冻期为 1 天)。
留神：你不能同时参加多笔交易（你必须在再次购买前发售掉之前的股票）。示例 1:
输出: prices = [1,2,3,0,2]
输入: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2:输出: prices = [1]
输入: 0提醒：
1 <= prices.length <= 5000
0 <= prices[i] <= 1000
状态转移方程
dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])//冷却工夫1天，所以要从 i - 2 天转移状态//买入，卖出 ---- 冷冻期 ---- 买入，卖出dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 2][k - 1][0] - prices[i])题目不限度k的大小，能够舍去
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])dp[i][1] = Math.max(dp[i - 1][1], dp[i - 2][0] - prices[i])//降维idp[0] = Math.max(dp[0], dp[1] + prices[i])dp[1] = Math.max(dp[1], profit_freeze - prices[i])残缺代码
const maxProfit = function (prices) { let n = prices.length; let buy = -prices[0];//手中有股票 let sell = 0;//没有股票 let profit_freeze = 0; for (let i = 1; i < n; i++) { let temp = sell; sell = Math.max(sell, buy + prices[i]); buy = Math.max(buy, profit_freeze - prices[i]); profit_freeze = temp; } return sell;};714. 交易股票的最佳时机含手续费 (medium) 每次交易含手续费
给定一个整数数组 prices，其中 prices[i]示意第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
你能够有限次地实现交易，然而你每笔交易都须要付手续费。如果你曾经购买了一个股票，在卖出它之前你就不能再持续购买股票了。
返回取得利润的最大值。
留神：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只须要为领取一次手续费。
示例 1：
输出：prices = [1, 3, 2, 8, 4, 9], fee = 2
输入：8
解释：可能达到的最大利润:
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8
示例 2：输出：prices = [1,3,7,5,10,3], fee = 3
输入：6提醒：
1 <= prices.length <= 5 * 104
1 <= prices[i] < 5 * 104
0 <= fee < 5 * 104
状态转移方程
//每次交易要领取手续费 咱们定义在卖出的时候扣手续费dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee)dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])残缺代码
const maxProfit = function (prices, fee) { let sell = 0;//卖出 let buy = -prices[0];//买入 for (let i = 1; i < prices.length; i++) { sell = Math.max(sell, buy + prices[i] - fee); buy = Math.max(buy, sell - prices[i]); } return sell;};0-1背包问题
0-1背包问题指的是有n个物品和容量为j的背包，weight数组中记录了n个物品的分量，地位i的物品分量是weight[i]，value数组中记录了n个物品的价值，地位i的物品价值是vales[i]，每个物品只能放一次到背包中，问将那些物品装入背包，使背包的价值最大。
举例：
咱们用动静布局的形式来做
- 状态定义：
dp[i][j]示意从前i个物品里任意取，放进容量为j的背包，价值总和最大是多少 状态转移方程：
dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - weight[i]] + value[i]); 每个物品有放入背包和不放入背包两种状况- 当
j - weight[i]<0：示意装不下i号元素了，不放入背包，此时dp[i][j] = dp[i - 1][j]，dp[i] [j]取决于前i-1中的物品装入容量为j的背包中的最大价值 - 当
j - weight[i]>=0：能够抉择放入或者不放入背包。
放入背包则：dp[i][j] = dp[i - 1][j - weight[i]] + value[i]，dp[i - 1][j - weight[i]]示意i-1中的物品装入容量为j-weight[i]的背包中的最大价值，而后在加上放入的物品的价值value[i]就能够将状态转移到dp[i][j]。
不放入背包则：dp[i][j] = dp[i - 1] [j]，在这两种状况中取较大者。
- 当
初始化dp数组：
dp[i][0]示意背包的容积为0，则背包的价值肯定是0，dp[0][j]示意第0号物品放入背包之后背包的价值- 最终须要返回值：就是dp数组的最初一行的最初一列
循环实现之后的dp数组如下图
js：
function testWeightBagProblem(wight, value, size) { const len = wight.length, dp = Array.from({ length: len + 1 }).map(//初始化dp数组 () => Array(size + 1).fill(0) ); //留神咱们让i从1开始，因为咱们有时会用到i - 1，为了避免数组越界 //所以dp数组在初始化的时候，长度是wight.length+1 for (let i = 1; i <= len; i++) { for (let j = 0; j <= size; j++) { //因为weight的长度是wight.length+1，并且物品下标从1开始，所以这里i要减1 if (wight[i - 1] <= j) { dp[i][j] = Math.max( dp[i - 1][j], value[i - 1] + dp[i - 1][j - wight[i - 1]] ) } else { dp[i][j] = dp[i - 1][j]; } } } return dp[len][size];}function test() { console.log(testWeightBagProblem([1, 3, 4], [15, 20, 30], 4));}test();状态压缩
依据状态转移方程dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])，第i行只与第i-1行状态相干，所以咱们能够用滚动数组进行状态压缩，其次咱们留神到，j只与j后面的状态相干，所以只用一个数组从后向前计算状态就能够了。
动画过大，点击查看
function testWeightBagProblem2(wight, value, size) { const len = wight.length, dp = Array(size + 1).fill(0); for (let i = 1; i <= len; i++) { //从后向前计算，如果从前向后的话，最新的值会笼罩老的值，导致计算结果不正确 //dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - wight[i - 1]] + value[i - 1]) for (let j = size; j >= wight[i - 1]; j--) { dp[j] = Math.max(dp[j], dp[j - wight[i - 1]] + value[i - 1] ); } } return dp[size];}416. 宰割等和子集 （medium）
给你一个 只蕴含正整数 的 非空 数组 nums 。请你判断是否能够将这个数组宰割成两个子集，使得两个子集的元素和相等。
示例 1：
输出：nums = [1,5,11,5]
输入：true
解释：数组能够宰割成 [1, 5, 5] 和 [11] 。
示例 2：输出：nums = [1,2,3,5]
输入：false
解释：数组不能宰割成两个元素和相等的子集。提醒：
1 <= nums.length <= 200
1 <= nums[i] <= 100
- 思路：本题能够看成是0-1背包问题，给一个可装载重量为
sum / 2的背包和 N 个物品，每个物品的分量记录在 nums 数组中，问是否在一种装法，可能恰好将背包装满？dp[i][j]示意前i个物品是否能装满容积为j的背包，当dp[i][j]为true时示意恰好能够装满。每个数都有放入背包和不放入两种状况，分析方法和0-1背包问题一样。 - 复杂度：工夫复杂度
O(n*sum)，n是nums数组长度，sum是nums数组元素的和。空间复杂度O(n * sum)，状态压缩之后是O(sum)
js：
//能够看成是0-1背包问题，给一个可装载重量为 sum / 2 的背包和 N 个物品，//每个物品的分量记录在 nums 数组中，问是否在一种装法，可能恰好将背包装满？var canPartition = function (nums) { let sum = 0 let n = nums.length for (let i = 0; i < n; i++) { sum += nums[i] } if (sum % 2 !== 0) {//如果是奇数，那么宰割不了，间接返回false return false } sum = sum / 2 //dp[i][j]示意前i个物品是否能装满容积为j的背包，当dp[i][j]为true时示意恰好能够装满 //最初求的是 dp[n][sum] 示意前n个物品是否把容量为sum的背包恰好装满 //dp数组长度是n+1，而且是二维数组，第一维示意物品的索引，第二个维度示意背包大小 let dp = new Array(n + 1).fill(0).map(() => new Array(sum + 1).fill(false)) //dp数组初始化，dp[..][0] = true示意背包容量为0，这时候就曾经装满了， //dp[0][..] = false 示意没有物品，必定装不满 for (let i = 0; i <= n; i++) { dp[i][0] = true } for (let i = 1; i <= n; i++) {//i从1开始遍历避免取dp[i - 1][j]的时候数组越界 let num = nums[i - 1] //j从1开始，j为0的状况曾经在dp数组初始化的时候实现了 for (let j = 1; j <= sum; j++) { if (j - num < 0) {//背包容量有余 不能放入背包 dp[i][j] = dp[i - 1][j];//dp[i][j]取决于前i-1个物品是否能前好装满j的容量 } else { //dp[i - 1][j]示意不装入第i个物品 //dp[i - 1][j-num]示意装入第i个，此时须要向前看前i - 1是否能装满j-num //和背包的区别，这里只是返回true和false 示意是否装满，不必计算价值 dp[i][j] = dp[i - 1][j] || dp[i - 1][j - num]; } } } return dp[n][sum]};//状态转移方程 F[i, target] = F[i - 1, target] || F[i - 1, target - nums[i]]//第 n 行的状态只依赖于第 n-1 行的状态//状态压缩var canPartition = function (nums) { let sum = nums.reduce((acc, num) => acc + num, 0); if (sum % 2) { return false; } sum = sum / 2; const dp = Array.from({ length: sum + 1 }).fill(false); dp[0] = true; for (let i = 1; i <= nums.length; i++) { //从后向前计算，如果从前向后的话，最新的值会笼罩老的值，导致计算结果不正确 for (let j = sum; j > 0; j--) { dp[j] = dp[j] || (j - nums[i] >= 0 && dp[j - nums[i]]); } } return dp[sum];};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];};视频解说：传送门