# 【题库】动态规划DP刷题
# 爬楼梯（每次只能走一阶或两阶）
f(n) = f(n - 1) + f(n - 2)
f(1) = 1
f(2) = 2
实现也非常简单：
const fn = n => {
if (n <= 0) return 0
if (n === 1) return 1
if (n === 2) return 2
return fn(n - 1) + fn(n - 2)
}
# 最小编辑距离
最小编辑距离是指一个单词通过新增、替换、删除三种操作方法，变为另一个单词的最小操作数。使用DP动态规划解决，算法如下：
代码实现如下：
const dp = (a, b) => {
// 1. 初始化二维矩阵
let lenA = a.length;
let lenB = b.length;
let d = [];
d[0] = [];
// 2. 二维矩阵填值
// 填充第一行
for (let j = 0; j <= lenB; j++) {
d[0].push(j);
}
// 填充第一列
for (let i = 0; i <= lenA; i++) {
if (d[i]) {
d[i][0] = i;
} else {
d[i] = [];
d[i][0] = i;
}
}
// 3. DP求解矩阵每个位置的值
for (let i = 1; i <= lenA; i++) {
for (let j = 1; j <= lenB; j++) {
if (a[i - 1] === b[j - 1]) {
d[i][j] = d[i - 1][j - 1];
} else {
let m1 = d[i - 1][j] + 1;
let m2 = d[i][j - 1] + 1;
let m3 = d[i - 1][j - 1] + 1;
d[i][j] = Math.min(m1, m2, m3);
}
}
}
return d[lenA][lenB];
}
关于这道题目详细的讨论在这里，可自行阅读：最小编辑距离问题：递归与动态规划 (opens new window)
# 最长回文子串
回文天然具有「状态转移」性质：一个长度严格大于 2 的回文去掉头尾字符以后，剩下的部分依然是回文。反之，如果一个字符串头尾两个字符都不相等，那么这个字符串一定不是回文。
定义状态
dp[i][j] 表示子串 s[i..j] 是否为回文子串，这里子串 s[i..j] 定义为左闭右闭区间，即可以取到 s[i] 和 s[j]。
定义状态转移方程
dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]
代码实现：
const longestPalindrome = s => {
let len = s.length;
if (len < 2) {
return s;
}
let maxLen = 1;
let begin = 0;
// dp[i][j] 表示 s[i, j] 是否是回文串
let dp = new Array(len).fill([new Array(len).fill(false)])
const charArray = s.split('')
for (let i = 0; i < len; i++) {
dp[i][i] = true;
}
for (let j = 1; j < len; j++) {
for (let i = 0; i < j; i++) {
if (charArray[i] != charArray[j]) {
dp[i][j] = false;
} else {
if (j - i < 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
// 只要 dp[i][j] == true 成立，就表示子串 s[i..j] 是回文，此时记录回文长度和起始位置
if (dp[i][j] && j - i + 1 > maxLen) {
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substring(begin, begin + maxLen);
}
# 二维矩阵计算走法种类
问题1：有一个每排m、每列n个元素的二维矩阵，请问从左上角走到右下角总共有多少种不同的路线？
/**
*
* @param {*} m 一排有多少个
* @param {*} n 一列有多少个
* @returns 在有从左上角走到右下角的路径总和
*/
const transStepNoBlock = (m, n) => {
// 方法1：排列组合
// 总共要走 m+n-2 步
// 其中有 m-1 步向右，n-1步向左
// 只需奥在 m+n-2 中选择 m-1 步即可
// 方法2：动态规划
// 状态定义：DP[i,j] 表示从左上角走到第i行第j列的全部路线总数
// 初始状态：DP[0,0]=1
// 状态转移方程：DP[i,j]=
// 1. DP[i,j]=DP[i-1,j]+DP[i,j-1] if i>0,j>0 非首行首列元素，需要累加从左侧元素和从上侧元素到达的路径总和
// 2. DP[i,j]=DP[i-1,j] if j=0 首列非首个元素，直接取从上侧元素达到的总数即可
// 3. DP[i,j]=DP[i,j-1] if i=0 首行非首个元素，直接取从左侧元素达到的总数即可
// 填充完二维数组，取 DP[m-1,n-1] 即可
// 边界判断
if (m < 1 || n < 1) {
return 0
}
// 初始化dp矩阵
const dp = new Array(n).fill([]).map(i => new Array(m).fill(0))
// 填充左上角的一个值
dp[0][0] = 1
// 填充第一行
for (let i = 1; i < m; i++) {
dp[0][i] = dp[0][i - 1]
}
// 填充第一列
for (let j = 1; j < n; j++) {
dp[j][0] = dp[j - 1][0]
}
// 填充非首行首列
for (let i = 1; i < n; i++) {
for (let j = 1; j < m; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
}
}
// 返回结果
return dp[n - 1][m - 1]
}
问题2：有一个每排m、每列n个元素的二维矩阵，其中存在障碍物，数值为1代表畅通，数值为0代表障碍，请问从左上角走到右下角总共有多少种不同的路线？
/**
*
* @param {*} matrix 二维数组，0表示阻碍，1表示畅通能走
*/
const transStepWithBlock = (matrix) => {
// 方法：动态规划
// 状态定义：DP[i,j] 表示从左上角走到第i行第j列的全部路线总数
// 初始状态：DP[0,0]=1
// 状态转移方程：DP[i,j]=
// 1. DP[i,j]=DP[i-1,j]+DP[i,j-1] if i>0,j>0 && DP[i-1,j]=1 && DP[i,j-1]=1 非首行首列元素，需要累加从左侧元素和从上侧元素到达的路径总和
// DP[i,j]=DP[i-1,j] if i>0,j>0 && DP[i-1,j]=1 && DP[i,j-1]=0 非首行首列元素，需要累加从左侧元素和从上侧元素到达的路径总和
// DP[i,j]=DP[i,j-1] if i>0,j>0 && DP[i-1,j]=0 && DP[i,j-1]=1 非首行首列元素，需要累加从左侧元素和从上侧元素到达的路径总和
// 2. DP[i,j]=DP[i-1,j] if j=0 && DP[i-1,j]=1 首列非首个元素，直接取从上侧元素达到的总数即可
// DP[i,j]=0 if j=0 && DP[i-1,j]=0 首列非首个元素，直接取从上侧元素达到的总数即可
// 3. DP[i,j]=DP[i,j-1] if i=0 && DP[i,j-1]=1 首行非首个元素，直接取从左侧元素达到的总数即可
// DP[i,j]=0 if i=0 && DP[i,j-1]=0 首行非首个元素，直接取从左侧元素达到的总数即可
// 填充完二维数组，取 DP[m-1,n-1] 即可
const m = matrix[0].length // 列数
const n = matrix.length // 行数
// 边界判断
if (m < 1 || n < 1) {
return 0
}
// 初始化dp矩阵
const dp = new Array(n).fill([]).map(i => new Array(m).fill(0))
// 填充左上角的一个值
dp[0][0] = 1
// 填充第一行
for (let i = 1; i < m; i++) {
dp[0][i] = matrix[0][i - 1] === 1 ? dp[0][i - 1] : 0
}
// 填充第一列
for (let j = 1; j < n; j++) {
dp[j][0] = matrix[j - 1][0] === 1 ? dp[j - 1][0] : 0
}
// 填充非首行首列
for (let i = 1; i < n; i++) {
for (let j = 1; j < m; j++) {
const top = matrix[i][j - 1]
const left = matrix[i - 1][j]
if (top === 1) {
if (left === 1) { // 上、左都通
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
} else { // 上通、左不通
dp[i][j] = dp[i][j - 1]
}
} else {
if (left === 1) { // 上不通，左通
dp[i][j] = dp[i - 1][j]
} else { // 上、左都不通
dp[i][j] = 0
}
}
}
}
// 返回结果
return dp[n - 1][m - 1]
}
# 三角形最小路径之和(m 层)
状态定义：DP[i][j]——从底部走到[i][j]的所有路径最小和
状态转移方程：
dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]
定义初始值：
DP[m-1][j]=T[m-1][j]
// 返回dp[0][0]即可
function minPath(triangle) {
if (triangle.length === 0) {
return;
}
let dp = [];
for (let i = 0; i < triangle.length; i++) {
dp[i] = [];
for (let j = 0; j < triangle[i].length; j++) {
dp[i].push(0);
}
}
// 初始化
for (let i = 0; i < dp.length; i++) {
dp[dp.length - 1][i] = triangle[dp.length - 1][i];
}
// 递归
for (let i = dp.length - 2; i >= 0; i--) {
for (let j = 0; j < dp[i].length; j++) {
dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j];
}
}
return dp[0][0];
}
# 乘积最大子序列 (2 3 -2 4)
这里的状态是二维的，不只是一维，需要同时存 max 和 min，因为元素可能为负数
形式1：采用二维数组
DP[i, j] = [max, min]
if (a[i] > 0) DP[i, 0] = DP[i - 1, 0] * a[i]
if (a[i] < 0) DP[i, 0] = DP[i - 1, 1] * a[i]
if (a[i] > 0) DP[i, 1] = DP[i - 1, 1] * a[i]
if (a[i] < 0) DP[i, 1] = DP[i - 1, 0] * a[i]
结果： 遍历 DP[i, 0]，找出最大值
形式2：采用两个变量max、min存储
每有一个新的数字加入，最大值为当前最大值 x 新数，或当前最小值（负数） x 新数（负数），否则为当前值
function maxProduct(nums) {
if (typeof nums[0] === 'undefined' || nums.length === 0) {
return 0;
};
let max = nums[0],
min = nums[0],
result = nums[0];
for (let i = 1; i < nums.length; i++) {
let temp = max;
// 最大值的几种情况
// 1. 当前最大值max x 新数num[i] if num[i]>0
// 2. 当前最小值min x 新数num[i] if num[i]<0
// 3. 当前值 num[i]
max = Math.max(Math.max(max * nums[i], min * nums[i]), nums[i]);
// 最小值的几种情况
// 1. 当前最大值max x 新数num[i] if num[i]<0
// 2. 当前最小值min x 新数num[i] if num[i]>0
// 3. 当前值 num[i]
min = Math.min(Math.min(temp * nums[i], min * nums[i]), nums[i]);
if(max > result) {
result = max;
};
};
return result;
};
# 最长上升子序列(位置不变)
状态定义: DP[i] 表示到第 i 个数(选上 i 元素)的最优子结构
结果: DP[0]到 DP[n-1]的最大值
状态转移方程: DP[i]=max(DP[j])+1 (j 从 0 到 i-1,且 a[j]<a[i])
// dp[i] 表示以第i个元素结尾的最长上升子序列的长度
// 如果dp[i]<dp[j]+1,则dp[i]=dp[j]+1
// 初始化dp[0]=1
// 返回max(dp[0],dp[1],……,dp[n-1])的最大值
function lengthOfLIS(nums) {
if (nums.length === 0) return 0;
let dp = [1];
for (let i = 1; i < nums.length; i++) {
dp.push(0);
}
let LIS = 1;
for (let i = 1; i < dp.length; i++) {
dp[i] = 1;
for (let j = 0; j < i; j++) {
if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
}
}
if (LIS < dp[i]) {
LIS = dp[i];
}
}
return LIS;
}
# 零钱兑换问题
状态定义：DP[i] 表示凑成 i 的最小零钱总数
状态转移方程：DP[i] = min(DP[i - coin[j]]) + 1
// 给定4种面额的硬币1分，2分，5分，6分，如果要找11分的零钱，怎么做才能使得找的硬币数量总和最少。
// 动态方程： dp[i] = max(dp[i - 1], dp[i - 2], dp[i - 5], dp[i - 6]) + 1
function coinChange(coins, amount) {
let dp = [];
for (let i = 0; i <= amount; i++) {
dp.push(-1);
}
dp[0] = 0;
for (let i = 1; i <= amount; i++) {
for (let j = 0; j < coins.length; j++) {
if (i - coins[j] >= 0 && dp[i - coins[j]] !== -1) {
if (dp[i] === -1 || dp[i] > dp[i - coins[j]] + 1) {
dp[i] = dp[i - coins[j]] + 1;
}
}
}
}
return dp[amount];
}
# 背包问题
# 01背包
有n件物品和1个容量为W的背包。每种物品均只有一件，第i件物品的重量为weights[i]，价值为values[i]，求解将哪些物品装入背包可使价值总和最大。
dp( i,j ) = Max( dp( i-1, j ), dp( i-1, j-w[i] ) + v[i] ) // DP[k,w]表示当背包容量还剩 w 时,在前 k 个物品中选择的最大价值
DP[k, w] = DP[k - 1, w] //(当第 k 件过重, 超出总容量)
DP[k, w] = max(DP[k - 1, w], DP[k - 1][w(总) - w(k)] + v[k]) //前者表示放入第 k 个物品, 后者表示不放入第 k 个物品
/**
*
* @param {*} n 总共有n件物品
* @param {*} W 背包能承受的最大重量为W
* @param {*} weights 重量数组，n个元素
* @param {*} values 价值数组，n个元素
* @param {*} selected 是否选择数组，n个元素，0代表未被选中，1代表被选中
* @returns 背包能装物品的最大总价值
*/
function knapsack(n, W, weights, values, selected) {
//当物品数量为0，或者背包容量为0时，最优解为0
if (n == 0 || W == 0) {
return 0;
}
//从当前所剩物品的最后一个物品开始向前，逐个判断是否要添加到背包中
for (let i = n - 1; i >= 0; i--) {
//如果当前要判断的物品重量大于背包当前所剩的容量，那么就不选择这个物品
if (weights[i] > W) {
return knapsack(n - 1, W, weights, values, selected);
} else {
//不选择物品i的情况下的最优解
let a = knapsack(n - 1, W, weights, values, selected);
//选择物品i的情况下的最优解
let b = values[i] + knapsack(n - 1, W - weights[i], weights, values, selected);
//返回选择物品i和不选择物品i中最优解大的一个
if (a > b) {
selected[i] = 0; //物品i未被选取
return a; // 最大总价值
} else {
selected[i] = 1; //物品i被选取
return b; // 最大总价值
}
}
}
}
const selected = []
const ws = [2, 2, 6, 5, 4]
const vs = [6, 3, 5, 4, 6]
let maxValue = knapsack(5, 10, ws, vs, selected)
console.log(maxValue) //15
selected.forEach((el, i) => {
if (el) {
console.log("选择了物品" + i + "，其重量为" + ws[i] + "，其价值为" + vs[i])
}
})
# 完全背包
有n件物品和1个容量为W的背包。每种物品没有上限，第i件物品的重量为weights[i]，价值为values[i]，求解将哪些物品装入背包可使价值总和最大。
与01背包的区别是，这里每一种物品的个数都没有上限，01背包却规定了每一种物品只有一件。
function unboundedKnapsack(weights, values, W) {
// 总共有n类物品
let n = weights.length,
// f[i]代表前i类物品中能放入背包的最大价值总和
f = new Array(W + 1).fill(0);
for (let i = 0; i < n; i++) {
for (j = weights[i]; j <= W; j++) {
let tmp = f[j - weights[i]] + values[i]; // 将第i件物品也放入背包的最大价值总和
f[j] = (f[j] > tmp) ? f[j] : tmp;
}
}
return f[W];
}
let a = unboundedKnapsack([3, 2, 2], [5, 10, 20], 5); //输出40
console.log(a);
let b = unboundedKnapsack([2, 3, 4, 7], [1, 3, 5, 9], 10); //输出12
console.log(b);
# 多重背包
有n件物品和1个容量为W的背包。每种物品最多有numbers[i]件可用，第i件物品的重量为weights[i]，价值为values[i]，求解将哪些物品装入背包可使价值总和最大。
与完全背包的区别是，这里每一种物品都规定了使用上限，而不是无限使用。
function knapsack(weights, values, numbers, W) {
let n = weights.length;
let f = new Array(W + 1).fill(0)
for (let i = 0; i < n; i++) {
for (let k = 0; k < numbers[i]; k++) //其实就是把这类物品展开，调用numbers[i]次01背包代码
for (let j = W; j >= weights[i]; j--)//正常的01背包代码
f[j] = Math.max(f[j], f[j - weights[i]] + values[i]);
}
return f[W];
}
let maxValue = knapsack([2, 3, 1], [2, 3, 4], [1, 4, 1], 6)
console.log(maxValue) // 9
以上都是一些很经典的动态规划题，练习了这么多，相信你已经理解了动态规划解题的精髓了吧？总结一下，动态规划的题目一般的解题步骤是：（1）定义状态，即DP[i]代表什么含义；（2）定义状态转移方程，即DP数组的各值是如何求得的；（3）定义初始化状态，即DP数组有哪些初始值；（4）写代码~ 其实在我们解题的过程中，如果发现求解需要不断依赖之前计算的结果，这时可以考虑DP算法，能大大提高求解效率。