动态规划

时游大约 14 分钟

动态规划

动态规划是将小问题的解汇集成大问题的答案，一步步引导我们走向解决问题的彼岸。

初探动态规划

动态规划是一个重要的算法范式，它将一个问题分解为一系列更小的子问题，并通过存储子问题的解来避免重复计算，从而大幅度提升算法效率。

爬楼梯问题

给定一个共有n阶的楼梯，你每一步可以向上1个或2个台阶，请问有多少种方案可以爬升到楼顶？

如下图所示，对于一个3阶楼梯，共有3种方案可以爬到楼顶。爬到第 3 阶的方案数量

/* 回溯 */
function backtrack(choices, state, n, res) {
	if (state === n) res.set(0, res.get(0) + 1);

	// 遍历所有选择
	for (const choice of choices) {
		// 剪枝：不允许越过第 n 阶
		if (state + choice > n) continue;
		// 尝试：做出选择，更新状态
		backtrack(choices, state + choice, n, res);
	}
}

/* 爬楼梯：回溯 */
function climbingStairsBacktrack(n) {
	// 可选择
	let choices = [1, 2];
	// 从哪开始
	let state = 0;
	// 结果
	const res = new Map();
	res.set(0, 0); // 使用 res[0] 记录方案数量
	backtrack(choices, state, n, res);
	console.log(res);

	return res[0];
}

climbingStairsBacktrack(4);

方法一：暴力搜索

回溯算法通常并不显式地对问题进行拆解，而是将问题看作一系列决策步骤，通过试探和剪枝，搜索所有可能的解。

假设爬到第i阶共有dp[i]方案，那么dp[i]就是原问题，其子问题包括：dp[i-1],dp[i-2]……,dp[2],dp[1]。由于每轮只能上1阶或2阶，因此当我们站在第i阶楼梯上时，上一轮只能站在第i-1阶或第i-2阶上。由此可以得出一个重要推论：爬到第i-1阶加第i-2阶的方案数等于爬到第i阶的方案数。公式如下： dp[i] = dp[i-1] + dp[i-2]。

/* 搜索 */
function dfs(i) {
    // 已知 dp[1] 和 dp[2] ，返回之
    if (i === 1 || i === 2) return i;
    // dp[i] = dp[i-1] + dp[i-2]
    const count = dfs(i - 1) + dfs(i - 2);
    return count;
}

/* 爬楼梯：搜索 */
function climbingStairsDFS(n) {
    return dfs(n);
}

对于问题dp[n]，其递归深度为n，时间复杂度为 ${O(2^n)}$ ，呈现爆炸性增长。

指数阶的时间复杂度是“重叠子问题”导致的。例如dp[7],dp[8]等重复子问题。

方法二：记忆化搜索

为了提升算法效率，我们希望所有的重叠子问题都只被计算一次。因此我们声明一个变量mem来记录每个问题的子问题的解，并在搜索过程中将重叠子问题进行剪枝。

(1) 当首次计算dp[i]时，将其解记录到mem中。 (2) 再次计算dp[i]时，直接从mem中取出结果，避免重复计算。

/* 记忆化搜索 */
function dfs(i, mem) {
    // 已知 dp[1] 和 dp[2] ，返回之
    if (i === 1 || i === 2) return i;
    // 若存在记录 dp[i] ，则直接返回之
    if (mem[i] != -1) return mem[i];
    // dp[i] = dp[i-1] + dp[i-2]
    const count = dfs(i - 1, mem) + dfs(i - 2, mem);
    // 记录 dp[i]
    mem[i] = count;
    return count;
}

/* 爬楼梯：记忆化搜索 */
function climbingStairsDFSMem(n) {
    // mem[i] 记录爬到第 i 阶的方案总数，-1 代表无记录
    const mem = new Array(n + 1).fill(-1);
    return dfs(n, mem);
}

经过记忆化处理后，所有重叠子问题都只需计算一次，时间复杂度优化至 ${O(n)}$ 。

方法三：动态规划

记忆化搜索是一种“从顶至底”的方法：我们从原问题(根节点)开始，递归地将较大子问题分解为较小子问题，直到解已知的最小子问题后，通过回溯收集各层子问题的解，最终汇集成原问题的解。

相反的，动态规划是一种“从底至顶”的方法：从最小子问题的解开始，迭代地构建更大子问题的解，直到得到原问题的解。

/* 爬楼梯：动态规划 */
function climbingStairsDP(n) {
    if (n === 1 || n === 2) return n;
    // 初始化 dp 表，用于存储子问题的解
    const dp = new Array(n + 1).fill(-1);
    // 初始状态：预设最小子问题的解
    dp[1] = 1;
    dp[2] = 2;
    // 状态转移：从较小子问题逐步求解较大子问题
    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

专业术语：

将数组dp称为dp表，dp[i]表示状态i对应子问题的解。
将最小子问题对应的状态(第一阶和第二阶台阶)称为初始状态。
将递推公式dp[i] = dp[i-1] + dp[i-2]称为状态转移方程。

空间优化

由于dp[i]只跟dp[i-1]和dp[i-2]有关，因此我们无须使用一个数组dp来存储所有子问题的解，只需要两个变量滚动前进即可。

/* 爬楼梯：空间优化后的动态规划 */
function climbingStairsDPComp(n) {
    if (n === 1 || n === 2) return n;
    let a = 1,
        b = 2;
    for (let i = 3; i <= n; i++) {
        const tmp = b;
        b = a + b;
        a = tmp;
    }
    return b;
}

以上代码的空间复杂度从 ${O(n)}$ 降到了 ${O(1)}$ 。

在动态规划中，当前状态仅与前面有限个状态有关，这是就可以只保留必要的状态，通过降维来节省空间，这种技巧被称为“滚动变量”或“滚动数组”。

动态规划问题特性

子问题分解是一种通用的算法思路，在分治、动态规划、回溯中的侧重点不同。

分治算法递归地将原问题划分为多个相互独立的子问题，直到最小子问题，并在回溯中合并子问题的解，最终得到原问题的解。
动态规划也对问题进行递归分解，但与分治算法的主要区别是，动态规划中的子问题是相互依赖的，在分解过程中会出现许多重叠子问题。
回溯算法在尝试和回退中穷举所有可能的解，并通过剪枝避免不必要的搜索分支。原问题的解由一系列决策步骤构成，我们可以将每个决策步骤之前的子序列看作一个子问题。

实际上，动态规划常用来求解最优化问题，它们不仅包含重叠子问题，还具有另外两大特性：最优子结构、无后效性。

最优子结构

给定一个楼梯，你每一次可以上1步或2步，每一阶楼梯上都贴有一个非负整数，代表你在该台阶所需付出的代价。给定一个非负整数数组cost，其中cost[i]表示在i级台阶所需要付出的代价。，cost[0]代表地面，请计算最少需要付出多少代价才能到达顶部？

设dp[i]为爬到第i阶所累计付出的代价，由于第i阶只能从第i-1阶和第i-2阶过来，因此dp[i]只可能等于dp[i-1] + cost[i]或dp[i-2] + cost[i]，为了减少代价，应当选取其中较小的。因此状态转移方程为：dp[i] = min(dp[i-1],dp[i-2]) + cost[i]。

/* 爬楼梯最小代价：动态规划 */
function minCostClimbingStairsDP(cost) {
    const n = cost.length - 1;
    if (n === 1 || n === 2) {
        return cost[n];
    }
    // 初始化 dp 表，用于存储子问题的解
    const dp = new Array(n + 1);
    // 初始状态：预设最小子问题的解
    dp[1] = cost[1];
    dp[2] = cost[2];
    // 状态转移：从较小子问题逐步求解较大子问题
    for (let i = 3; i <= n; i++) {
        dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
    }
    return dp[n];
}

采用滚动数组降低空间复杂度

/* 爬楼梯最小代价：空间优化后的动态规划 */
function minCostClimbingStairsDPComp(cost) {
    const n = cost.length - 1;
    if (n === 1 || n === 2) {
        return cost[n];
    }
    let a = cost[1],
        b = cost[2];
    for (let i = 3; i <= n; i++) {
        const tmp = b;
        b = Math.min(a, tmp) + cost[i];
        a = tmp;
    }
    return b;
}

无后效性

无后效性是动态规划能够有效解决问题的重要特性之一，其定义为：给定一个确定的状态，它的未来发展只与当前状态有关，而与过去的经历的所有状态无关。

带约束爬楼梯：给定一个有n阶的楼梯，每步可以走1层或2层，但是不能连续两轮走1层，请问有多少种方案可以到楼顶？

/* 带约束爬楼梯：动态规划 */
function climbingStairsConstraintDP(n) {
    if (n === 1 || n === 2) {
        return 1;
    }
    // 初始化 dp 表，用于存储子问题的解，
    dp[1][1] = 1;
    dp[1][2] = 0;
    dp[2][1] = 0;
    dp[2][2] = 1;
    // 状态转移：从较小子问题逐步求解较大子问题
    for (let i = 3; i <= n; i++) {
        dp[i][1] = dp[i - 1][2];
        dp[i][2] = dp[i - 2][1] + dp[i - 2][2];
    }
    return dp[n][1] + dp[n][2];
}

动态规划解题思路

问题求解步骤

描述决策
定义状态
推导状态转移方程
确定边界
建立DP表

最短路径和

给定一个nxm的二位网格grid，网格中每个单元格都有一个非负整数，表示该单元格的代价。机器人从左上角单元格为起点，每次只能向左或向下移动，直到抵达右下角单元格。请返回最小的路径和。

// 状态转移方程为：dp[i,j] = Math.min(dp[i-1,j],dp[i,j-1]) + grid[i,j]
function minPathSumDp(arr: number[][]): number {
	if (arr.length == 0) return 0;
	// 初始化dp表
	let dp: number[][] = Array.from({ length: arr.length }, () =>
		Array.from({ length: arr[0].length }, () => 0)
	);
	dp[0][0] = arr[0][0];
	// 首行
	for (let i = 1; i < arr[0].length; i++) {
		dp[0][i] = dp[0][i - 1] + arr[0][i];
	}
	// 首列
	for (let i = 1; i < arr.length; i++) {
		dp[i][0] = dp[i - 1][0] + arr[i][0];
	}

	// 其他行 & 其他列
	for (let i = 1; i < arr.length; i++) {
		for (let j = 1; j < arr[0].length; j++) {
			dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + arr[i][j];
		}
	}

	return dp[dp.length - 1][dp[0].length - 1];
}

let path: number[][] = [
	[1, 3, 1, 5],
	[2, 2, 4, 2],
	[5, 3, 2, 1],
	[4, 3, 5, 2],
];
console.log(minPathSumDp(path));

// 时间复杂度为O(nm)、空间复杂度为O(nm)

0-1背包问题

给定n个物品，第i个物品的重量为wgt[i-1]、价值为val[i-1]，和一个容量为cap的背包。每个物品只能选择一次，问在限定背包容量下能放下物品的最大价值。

// 暴力搜索
function knapsackDfs(wgt = [], val = [], i = 0, capcity = 0) {
	// 无物品或无容量
	if (i == 0 || capcity == 0) return 0;

	// 超出剩余容量
	if (wgt[i - 1] > capcity) {
		return knapsackDfs(wgt, val, i - 1, capcity);
	}

	// 计算放入与不放入的最大价值
	let no = knapsackDfs(wgt, val, i - 1, capcity);
	let yes = knapsackDfs(wgt, val, i - 1, capcity - wgt[i - 1]) + val[i - 1];

	return Math.max(no, yes);
}

let res = knapsackDfs([1, 2, 3, 4, 5], [1, 6, 3, 1, 8], 5, 10);
console.log(res);


// 记忆搜索
function knapsackDfsMem(wgt = [], val = [], i = 0, capcity = 0, mem = []) {
	// 无物品或无容量
	if (i == 0 || capcity == 0) return 0;

	// 检查当前是否已记录
	if (mem[i][capcity] != -1) {
		return mem[i][capcity];
	}

	// 超出背包重量
	if (wgt[i - 1] > capcity) {
		return knapsackDfsMem(wgt, val, i - 1, capcity, mem);
	}

	// 计算放入与不放入的最大价值
	no = knapsackDfsMem(wgt, val, i - 1, capcity, mem);
	yes =
		knapsackDfsMem(wgt, val, i - 1, capcity - wgt[i - 1], mem) + val[i - 1];

	mem[i][capcity] = Math.max(no, yes);
	return mem[i][capcity];
}

let mem = Array.from({ length: 5 + 1 }, () => Array(10 + 1).fill(-1));

let memRes = knapsackDfsMem([1, 2, 3, 4, 5], [1, 6, 3, 1, 8], 5, 10, mem);

console.log(memRes);

// 动态规划
function knapsackDP(wgt, val, cap) {
	const n = wgt.length;
	// 初始化 dp 表
	const dp = Array(n + 1)
		.fill(0)
		.map(() => Array(cap + 1).fill(0));
	// 状态转移
	for (let i = 1; i <= n; i++) {
		for (let c = 1; c <= cap; c++) {
			if (wgt[i - 1] > c) {
				// 若超过背包容量，则不选物品 i
				dp[i][c] = dp[i - 1][c];
			} else {
				// 不选和选物品 i 这两种方案的较大值
				dp[i][c] = Math.max(
					dp[i - 1][c],
					dp[i - 1][c - wgt[i - 1]] + val[i - 1]
				);
			}
		}
	}
	return dp[n][cap];
}

let dpRes = knapsackDP([5,11,15],[1, 2, 3],  4);
console.log(dpRes);

// dp空间优化
function knapsackDPComp(wgt, val, cap) {
    const n = wgt.length;
    // 初始化 dp 表
    const dp = Array(cap + 1).fill(0);
    // 状态转移
    for (let i = 1; i <= n; i++) {
        // 倒序遍历
        for (let c = cap; c >= 1; c--) {
            if (wgt[i - 1] <= c) {
                // 不选和选物品 i 这两种方案的较大值
                dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[cap];
}

let dpRes = knapsackDPComp([5,11,15],[1, 2, 3],  4);
console.log(dpRes);

完全背包问题

给定n个物体，第i个物品的重量为wgt[i-1]、价值为val[i-1]，和一个容量为cap的背包。每个物品可以重复选择，问在限定背包容量下能放入物品的最大价值。

动态规划思路跟0-1背包问题很相似，区别仅在于不限制物品的选择次数。

function knapsackDP(wgt = [], val = [], cap = 0) {
   const n = wgt.length;
   // 初始化 dp 表
   const dp = Array(n + 1)
   	.fill(0)
   	.map(() => Array(cap + 1).fill(0));
   // 状态转移
   for (let i = 1; i <= n; i++) {
   	for (let c = 1; c <= cap; c++) {
   		if (wgt[i - 1] > c) {
   			// 若超过背包容量，则不选物品 i
   			dp[i][c] = dp[i - 1][c];
   		} else {
   			// 不选和选物品 i 这两种方案的较大值
   			dp[i][c] = Math.max(
   				dp[i - 1][c],
   				dp[i][c - wgt[i - 1]] + val[i - 1]
   			);
   		}
   	}
   }
   return dp[n][cap];
}

let res = knapsackDP([1, 2, 3], [5, 11, 15], 4);
console.log(res);

零钱兑换问题一

给定n种硬币，第i种硬币的面值为coins[i-1]，目标金额为amt，每种硬币可以重复选取，问能够凑出目标金额的最少银币数量。若无法凑出目标金额，返回-1。

/* 零钱兑换：动态规划 */
function coinChangeDP(coins, amt) {
	const n = coins.length;
	const MAX = amt + 1;
	// 初始化 dp 表
	const dp = Array.from({ length: n + 1 }, () =>
		Array.from({ length: amt + 1 }, () => 0)
	);
	// 状态转移：首行
	for (let a = 1; a <= amt; a++) {
		dp[0][a] = MAX;
	}
	// 状态转移：其余行和列
	for (let i = 1; i <= n; i++) {
		for (let a = 1; a <= amt; a++) {
			if (coins[i - 1] > a) {
				// 若超过目标金额，则不选硬币 i
				dp[i][a] = dp[i - 1][a];
			} else {
				// 不选和选硬币 i 这两种方案的较小值
				dp[i][a] = Math.min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1);
			}
		}
	}
	return dp[n][amt] !== MAX ? dp[n][amt] : -1;
}

let res = coinChangeDP([1, 5, 10, 20], 50);

console.log(res);

/* 零钱兑换：空间优化后的动态规划 */
function coinChangeDPComp(coins, amt) {
    const n = coins.length;
    const MAX = amt + 1;
    // 初始化 dp 表
    const dp = Array.from({ length: amt + 1 }, () => MAX);
    dp[0] = 0;
    // 状态转移
    for (let i = 1; i <= n; i++) {
        for (let a = 1; a <= amt; a++) {
            if (coins[i - 1] > a) {
                // 若超过目标金额，则不选硬币 i
                dp[a] = dp[a];
            } else {
                // 不选和选硬币 i 这两种方案的较小值
                dp[a] = Math.min(dp[a], dp[a - coins[i - 1]] + 1);
            }
        }
    }
    return dp[amt] !== MAX ? dp[amt] : -1;
}

零钱兑换问题二

给定n中硬币，第i种硬币面值为coins[i-1]，目标金额为amt，每种硬币可以重复选取，问凑出目标金额的硬币组合数量。

/* 零钱兑换 II：动态规划 */
function coinChangeIIDP(coins, amt) {
    const n = coins.length;
    // 初始化 dp 表
    const dp = Array.from({ length: n + 1 }, () =>
        Array.from({ length: amt + 1 }, () => 0)
    );
    // 初始化首列
    for (let i = 0; i <= n; i++) {
        dp[i][0] = 1;
    }
    // 状态转移
    for (let i = 1; i <= n; i++) {
        for (let a = 1; a <= amt; a++) {
            if (coins[i - 1] > a) {
                // 若超过目标金额，则不选硬币 i
                dp[i][a] = dp[i - 1][a];
            } else {
                // 不选和选硬币 i 这两种方案之和
                dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]];
            }
        }
    }
    return dp[n][amt];
}
/* 零钱兑换 II：动态规划 */
function coinChangeIIDP(coins, amt) {
    const n = coins.length;
    // 初始化 dp 表
    const dp = Array.from({ length: n + 1 }, () =>
        Array.from({ length: amt + 1 }, () => 0)
    );
    // 初始化首列
    for (let i = 0; i <= n; i++) {
        dp[i][0] = 1;
    }
    // 状态转移
    for (let i = 1; i <= n; i++) {
        for (let a = 1; a <= amt; a++) {
            if (coins[i - 1] > a) {
                // 若超过目标金额，则不选硬币 i
                dp[i][a] = dp[i - 1][a];
            } else {
                // 不选和选硬币 i 这两种方案之和
                dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]];
            }
        }
    }
    return dp[n][amt];
}

编辑距离问题

编辑距离，也称为Levenshtein距离，指两个字符串置换相互转换的最少修改次数，通常用于信息检索和自然语言处理中度量两个序列的相似度。

输入两个字符串s和t，返回将s转换为t所需的最少编辑次数，可以在一个字符串中进行插入、删除、替换任意字符的操作。

动态规划

# 动态规划

# 初探动态规划

# 方法一：暴力搜索

# 方法二：记忆化搜索

# 方法三：动态规划

# 空间优化

# 动态规划问题特性

# 最优子结构

# 无后效性

# 动态规划解题思路

# 问题求解步骤

# 最短路径和

# 0-1背包问题

# 完全背包问题

# 零钱兑换问题一

# 零钱兑换问题二

# 编辑距离问题

动态规划

初探动态规划

方法一：暴力搜索

方法二：记忆化搜索

方法三：动态规划

空间优化

动态规划问题特性

最优子结构

无后效性

动态规划解题思路

问题求解步骤

最短路径和

0-1背包问题

完全背包问题

零钱兑换问题一

零钱兑换问题二

编辑距离问题