什么是动态规划
动态规划，英文：Dynamic Programming，简称DP，将问题分解为互相重叠的子问题，通过反复求解子问题来解决原问题就是动态规划，如果某一问题有很多重叠子问题，使用动态规划来解是比较有效的。
求解动态规划的核心问题是穷举，但是这类问题穷举有点特别，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下。动态规划问题一定会具备「最优子结构」，才能通过子问题的最值得到原问题的最值。另外，虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，只有列出正确的「状态转移方程」才能正确地穷举。重叠子问题、最优子结构、状态转移方程就是动态规划三要素
动态规划和其他算法的区别
- 动态规划和分治的区别：动态规划和分治都有最优子结构 ，但是分治的子问题不重叠
- 动态规划和贪心的区别：动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优解，所以它永远是局部最优，但是全局的解不一定是最优的。
- 动态规划和递归的区别：递归和回溯可能存在非常多的重复计算，动态规划可以用递归加记忆化的方式减少不必要的重复计算
动态规划的解题方法
- 递归 记忆化(自顶向下)
- 动态规划（自底向上）
ds_135解动态规划题目的步骤
- 根据重叠子问题定义状态
- 寻找最优子结构推导状态转移方程
- 确定dp初始状态
- 确定输出值
斐波那契的动态规划的解题思路
ds_3动画过大，点击查看
暴力递归
代码语言：javascript复制//暴力递归复杂度O(2^n)
var fib = function (N) {
if (N == 0) return 0;
if (N == 1) return 1;
return fib(N - 1) fib(N - 2);
};递归 记忆化
代码语言：javascript复制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);
};动态规划
代码语言：javascript复制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];
};滚动数组优化
代码语言：javascript复制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;
};动态规划 降维，（降维能减少空间复杂度，但不利于程序的扩展）
代码语言：javascript复制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;
};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.动态规划
ds_71- 思路：因为每次可以爬 1 或 2 个台阶，所以到第n阶台阶可以从第n-2或n-1上来，其实就是斐波那契的dp方程
- 复杂度分析：时间复杂度
O(n)，空间复杂度O(1)
Js:
代码语言：javascript复制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;
}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 <= numsi <= 400
ds_148- 思路：
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：
代码语言：javascript复制//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;
};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
ds_136- 思路：
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：
代码语言：javascript复制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];
};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:
代码语言：javascript复制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.动态规划
ds_78
ds_79- 思路：
dp[i][j]表示 s 的前 i 个字符能否和p的前j个字符匹配，分为四种情况，看图 - 复杂度：时间复杂度
O(mn)，m,n分别是字符串s和p的长度，需要嵌套循环s和p。空间复杂度O(mn)，dp数组所占的空间
js:
代码语言：javascript复制//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串
};64. 最小路径和 (medium)
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。示例 1：
：因为路径 1→3→1→1→1 的总和最小。 示例 2：输入：grid = [1,2,3,4,5,6] 输出：12提示：m == grid.length n == gridi.length 1 <= m, n <= 200 0 <= gridi <= 100
ds_205- 思路：
dp[i][j]表示从矩阵左上角到（i，j）这个网格对应的最小路径和，只要从上到下，从左到右遍历网格，当前最小路径和就是当前的数值加上上面和左边左小的。 - 复杂度：时间复杂度
O(mn)，m、n分别是矩阵的长和宽。空间复杂度如果原地修改是O(1)，如果新建dp数组就是O(mn)
js：
代码语言：javascript复制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]
};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.动态规划
ds_76
ds_77- 思路：
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]，即dpi = dpi-1 1， 1指替换操作
- word1删除最后一个字符，状态转移成
- 如果
- 复杂度：时间复杂度是
O(mn)，m是word1的长度，n是word2的长度。空间复杂度是O(mn)，需要用m * n大小的二维数字存储状态。
Js:
代码语言：javascript复制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];
};62. 不同路径 （medium）
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？
= 3, n = 2 输出：3 解释： 从左上角开始，总共有 3 条路径可以到达右下角。向右 -> 向下 -> 向下 向下 -> 向下 -> 向右 向下 -> 向右 -> 向下示例 3：输入：m = 7, n = 3 输出：28 示例 4：输入：m = 3, n = 3 输出：6提示：1 <= m, n <= 100 题目数据保证答案小于等于 2 * 109
方法1.动态规划
动画过大，点击查看
- 思路:由于在每个位置只能向下或者向右， 所以每个坐标的路径和等于上一行相同位置和上一列相同位置不同路径的总和，状态转移方程：
f[i][j] = f[i - 1][j] f[i][j - 1]; - 复杂度:时间复杂度
O(mn)。空间复杂度O(mn)，优化后O(n)
js:
代码语言：javascript复制var uniquePaths = function (m, n) {
const f = new Array(m).fill(0).map(() => new Array(n).fill(0)); //初始dp数组
for (let i = 0; i < m; i ) {
//初始化列
f[i][0] = 1;
}
for (let j = 0; j < n; j ) {
//初始化行
f[0][j] = 1;
}
for (let i = 1; i < m; i ) {
for (let j = 1; j < n; j ) {
f[i][j] = f[i - 1][j] f[i][j - 1];
}
}
return f[m - 1][n - 1];
};
//状态压缩
var uniquePaths = function (m, n) {
let cur = new Array(n).fill(1);
for (let i = 1; i < m; i ) {
for (let r = 1; r < n; r ) {
cur[r] = cur[r - 1] cur[r];
}
}
return cur[n - 1];
};312. 戳气球 (hard)
有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 numsi - 1 numsi numsi 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 <= numsi <= 100
方法1:动态规划
ds_112- 思路：
dp[i][j]表示开区间(i,j)能拿到的的金币，k是这个区间 最后一个 被戳爆的气球，枚举i和j，遍历所有区间，i-j能获得的最大数量的金币等于 戳破当前的气球获得的金钱加上之前i-k、k-j区间中已经获得的金币 - 复杂度：时间复杂度
O(n^3)，n是气球的数量，三层遍历。空间复杂度O(n^2)，dp数组的空间。
js：
代码语言：javascript复制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];
};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
ds_204方法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：
代码语言：javascript复制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];
};视频讲解：传送门
