动态规划十大经典案例
动态规划是一种常用的算法思想，它可以解决很多优化问题，比如求最大值、最小值、最长子序列等。动态规划的基本思想是把一个复杂的问题分解成若干个子问题，然后从最简单的子问题开始，逐步推导出更大的子问题的解，最终得到原问题的解。动态规划通常需要定义一个状态数组，表示不同阶段的最优解，以及一个状态转移方程，表示如何从前面的状态推导出后面的状态。
本文将介绍动态规划的十大经典案例，分别是：
- 最大子序列和
- 零钱兑换
- 最长上升子序列
- 股票买卖
- 最长公共子序列
- 最长回文子序列
- 编辑距离
- 不同的二叉搜索树
- 矩阵链乘法
- 0-1背包问题
每个案例都会给出问题描述、算法思路、状态定义、状态转移方程和Java代码实现。如果你想了解更多细节和解释，请点击每个案例的链接查看。
1. 最大子序列和
问题描述
给定一个整数数组，找出其中连续的一段子数组，使得它们的和最大。
示例：
输入：[-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6。
算法思路
这个问题可以用一个一维数组dp来表示以每个位置结尾的最大子序列和，状态转移方程为dp [i] = max (dp [i-1] + nums [i], nums [i])。也就是说，对于每个位置i，我们要判断是把前面的最大子序列和加上当前元素，还是只取当前元素作为新的起点。最后我们遍历dp数组，找出其中的最大值即可。
状态定义
dp [i]：表示以第i个元素结尾的最大子序列和
状态转移方程
dp [i] = max (dp [i-1] + nums [i], nums [i])
Java代码实现
class Solution {
public int maxSubArray(int[] nums) {
// 边界条件判断
if (nums == null || nums.length == 0) {
return 0;
}
// 定义状态数组
int[] dp = new int[nums.length];
// 初始化第一个元素
dp[0] = nums[0];
// 定义结果变量
int result = dp[0];
// 遍历数组，根据状态转移方程更新dp数组和结果变量
for (int i = 1; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
result = Math.max(result, dp[i]);
}
// 返回结果
return result;
}
}
2. 零钱兑换
问题描述
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
示例 2:
输入: coins = [2], amount = 3
输出: -1
算法思路
这个问题可以用一个一维数组dp来表示凑成每个金额所需的最少硬币数，状态转移方程为dp [i] = min (dp [i], dp [i - coins [j]] + 1)，其中coins [j]是硬币面额。也就是说，对于每个金额i，我们要遍历所有的硬币面额，找出其中能使得dp [i]最小的那个硬币，然后加上1表示使用了这个硬币。最后我们返回dp [amount]即可，如果它等于amount + 1，说明没有找到合适的硬币组合，返回-1。
状态定义
dp [i]：表示凑成金额i所需的最少硬币数
状态转移方程
dp [i] = min (dp [i], dp [i - coins [j]] + 1)
Java代码实现
class Solution {
public int coinChange(int[] coins, int amount) {
// 边界条件判断
if (coins == null || coins.length == 0 || amount < 0) {
return -1;
}
// 定义状态数组
int[] dp = new int[amount + 1];
// 初始化状态数组为最大值
Arrays.fill(dp, amount + 1);
// 初始化第一个元素为0
dp[0] = 0;
// 遍历数组，根据状态转移方程更新dp数组
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (coin <= i) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
// 返回结果，如果等于最大值，说明没有找到合适的硬币组合，返回-1
return dp[amount] == amount + 1 ? -1 : dp[amount];
}
}
3. 最长上升子序列
问题描述
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
算法思路
这个问题可以用一个一维数组dp来表示以每个位置结尾的最长上升子序列的长度，状态转移方程为dp [i] = max (dp [j] + 1)，其中j是小于i且nums [j] < nums [i]的所有位置。也就是说，对于每个位置i，我们要遍历它之前的所有位置j，找出其中能使得dp [i]最大的那个位置j，然后加上1表示当前元素也属于这个子序列。最后我们遍历dp数组，找出其中的最大值即可。
状态定义
dp [i]：表示以第i个元素结尾的最长上升子序列的长度
状态转移方程
dp [i] = max (dp [j] + 1)，其中j是小于i且nums [j] < nums [i]的所有位置
Java代码实现
class Solution {
public int lengthOfLIS(int[] nums) {
// 边界条件判断
if (nums == null || nums.length == 0) {
return 0;
}
// 定义状态数组
int[] dp = new int[nums.length];
// 初始化状态数组，每个元素自身就是一个长度为1的上升子序列
for (int i = 0; i < nums.length; i++) {
dp[i] = 1;
}
// 定义一个变量记录最大值
int max = 1;
// 遍历数组，根据状态转移方程更新dp数组
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
// 如果当前元素大于之前的元素，说明可以构成一个上升子序列
// 那么就要比较以当前元素结尾和以之前元素结尾两种情况下的最长上升子序列的长度
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
// 更新最大值
max = Math.max(max, dp[i]);
}
// 返回结果
return max;
}
}
4. 股票买卖
问题描述
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易（买一次再卖一次）。
示例：
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：第二天买入，第三天卖出，这笔交易所能获得利润 = 6-2 = 4 。随后第五天买入，第六天卖出，这笔交易所能获得利润 = 3-0 = 3 。
算法思路
这个问题可以用一个二维数组dp来表示在第i天最多进行k笔交易的情况下的最大利润，状态转移方程为dp [k] [i] = max (dp [k] [i-1], dp [k-1] [j-1] + prices [i] - prices [j])，其中j是小于i的所有位置。也就是说，对于每个位置i，我们要遍历它之前的所有位置j，找出其中能使得dp [k] [i]最大的那个位置j，然后加上当前价格减去之前价格表示进行了一次交易。为了优化时间复杂度，我们可以用一个临时变量tmpMax来记录之前的最大值，这样就不用每次都遍历j了。最后我们返回dp [k] [n-1]即可，其中n是数组长度。
状态定义
dp [k] [i]：表示在第i天最多进行k笔交易的情况下的最大利润
状态转移方程
dp [k] [i] = max (dp [k] [i-1], dp [k-1] [j-1] + prices [i] - prices [j])
Java代码实现
class Solution {
public int maxProfit(int k, int[] prices) {
// 边界条件判断
if (prices == null || prices.length == 0 || k <= 0) {
return 0;
}
// 定义状态数组
int[][] dp = new int[k + 1][prices.length];
// 遍历数组，根据状态转移方程更新dp数组
for (int i = 1; i <= k; i++) {
// 定义临时变量记录之前的最大值
int tmpMax = -prices[0];
for (int j = 1; j < prices.length; j++) {
// 更新当前位置的最大利润
dp[i][j] = Math.max(dp[i][j - 1], prices[j] + tmpMax);
// 更新临时变量
tmpMax = Math.max(tmpMax, dp[i - 1][j - 1] - prices[j]);
}
}
// 返回结果
return dp[k][prices.length - 1];
}
} 5. 最长公共子序列
问题描述
给定两个字符串 text1 和 text2 ，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列 ，返回 0 。一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1：
输入：text1 = “abcde”, text2 = “ace”
输出：3
解释：最长的公共子序列是 “ace” ，它的长度为 3 。
示例 2：
输入：text1 = “abc”, text2 = “abc”
输出：3
解释：最长的公共子序列是 “abc” ，它的长度为 3 。
算法思路
这个问题可以用一个二维数组dp来表示text1的前i个字符和text2的前j个字符的最长公共子序列的长度，状态转移方程为dp [i] [j] = dp [i-1] [j-1] + 1，如果text1 [i-1] == text2 [j-1]，否则为dp [i] [j] = max (dp [i-1] [j], dp [i] [j-1])。也就是说，对于每个位置i和j，我们要判断它们对应的字符是否相等，如果相等，说明可以增加一个公共子序列的长度，否则，说明要从它们之前的状态中选择一个较大的值作为当前状态。最后我们返回dp [m] [n]即可，其中m和n是字符串的长度。
状态定义
dp [i] [j]：表示text1的前i个字符和text2的前j个字符的最长公共子序列的长度
状态转移方程
dp [i] [j] = dp [i-1] [j-1] + 1，如果text1 [i-1] == text2 [j-1]
dp [i] [j] = max (dp [i-1] [j], dp [i] [j-1])，如果text1 [i-1] != text2 [j-1]
Java代码实现
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
// 边界条件判断
if (text1 == null || text2 == null || text1.length() == 0 || text2.length() == 0) {
return 0;
}
// 定义状态数组
int[][] dp = new int[text1.length() + 1][text2.length() + 1];
// 遍历字符串，根据状态转移方程更新dp数组
for (int i = 1; i <= text1.length(); i++) {
for (int j = 1; j <= text2.length(); j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
// 如果当前字符相等，说明可以增加一个公共子序列的长度
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
// 如果当前字符不相等，说明要从之前的状态中选择一个较大的值作为当前状态
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// 返回结果
return dp[text1.length()][text2.length()];
}
} 6. 最长回文子序列
问题描述
给定一个字符串s，找到其中最长的回文子序列，并返回该序列的长度。可以假设s的最大长度为1000。
示例 1:
输入: “bbbab”
输出: 4
解释: 一个可能的最长回文子序列为 “bbbb”。
示例 2:
输入: “cbbd”
输出: 2
解释: 一个可能的最长回文子序列为 “bb”。
算法思路
这个问题可以用一个二维数组dp来表示s的第i个字符到第j个字符组成的子串中，最长的回文子序列的长度，状态转移方程为dp [i] [j] = dp [i+1] [j-1] + 2，如果s [i] == s [j]，否则为dp [i] [j] = max (dp [i+1] [j], dp [i] [j-1])。也就是说，对于每个位置i和j，我们要判断它们对应的字符是否相等，如果相等，说明可以增加两个回文子序列的长度，否则，说明要从它们之后和之前的状态中选择一个较大的值作为当前状态。最后我们返回dp [0] [n-1]即可，其中n是字符串的长度
状态定义
dp [i] [j]：表示s的第i个字符到第j个字符组成的子串中，最长的回文子序列的长度
状态转移方程
dp [i] [j] = dp [i+1] [j-1] + 2，如果s [i] == s [j]
dp [i] [j] = max (dp [i+1] [j], dp [i] [j-1])，如果s [i] != s [j]
Java代码实现
class Solution {
public int longestPalindromeSubseq(String s) {
// 边界条件判断
if (s == null || s.length() == 0) {
return 0;
}
// 定义状态数组
int[][] dp = new int[s.length()][s.length()];
// 初始化状态数组，对角线上的元素为1，表示单个字符是长度为1的回文子序列
for (int i = 0; i < s.length(); i++) {
dp[i][i] = 1;
}
// 遍历字符串，根据状态转移方程更新dp数组
// 注意要从后往前遍历，因为要用到后面的状态
for (int i = s.length() - 1; i >= 0; i--) {
for (int j = i + 1; j < s.length(); j++) {
if (s.charAt(i) == s.charAt(j)) {
// 如果当前字符相等，说明可以增加两个回文子序列的长度
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
// 如果当前字符不相等，说明要从之后和之前的状态中选择一个较大的值作为当前状态
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
// 返回结果
return dp[0][s.length() - 1];
}
}
7. 编辑距离
问题描述
给定两个单词 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来表示word1的前i个字符和word2的前j个字符之间的编辑距离，状态转移方程为dp [i] [j] = min (dp [i-1] [j], dp [i] [j-1], dp [i-1] [j-1]) + 1，如果word1 [i-1] != word2 [j-1]，否则为dp [i] [j] = dp [i-1] [j-1]。也就是说，对于每个位置i和j，我们要判断它们对应的字符是否相等，如果不相等，说明要进行一次操作，操作有三种可能：在word1中插入一个字符，或者删除一个字符，或者替换一个字符。我们要选择其中能使得dp [i] [j]最小的那种操作。如果相等，说明不需要操作，直接沿用之前的状态。最后我们返回dp [m] [n]即可，其中m和n是单词的长度。
状态定义
dp [i] [j]：表示word1的前i个字符和word2的前j个字符之间的编辑距离
状态转移方程
dp [i] [j] = min (dp [i-1] [j], dp [i] [j-1], dp [i-1] [j-1]) + 1，如果word1 [i-1] != word2 [j-1]
dp [i] [j] = dp [i-1] [j-1]，如果word1 [i-1] == word2 [j-1]
Java代码实现
class Solution {
public int minDistance(String word1, String word2) {
// 边界条件判断
if (word1 == null || word2 == null) {
return 0;
}
// 定义状态数组
int[][] dp = new int[word1.length() + 1][word2.length() + 1];
// 初始化状态数组，第一行和第一列表示空串到另一个串的编辑距离，等于另一个串的长度
for (int i = 0; i <= word1.length(); i++) {
dp[i][0] = i;
}
for (int j = 0; j <= word2.length(); j++) {
dp[0][j] = j;
}
// 遍历字符串，根据状态转移方程更新dp数组
for (int i = 1; i <= word1.length(); i++) {
for (int j = 1; j <= word2.length(); j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
// 如果当前字符相等，说明不需要操作，直接沿用之前的状态
dp[i][j] = dp[i - 1][j - 1];
} else {
// 如果当前字符不相等，说明要进行一次操作，操作有三种可能：插入，删除，替换
// 我们要选择其中能使得dp[i][j]最小的那种操作
dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
}
}
}
// 返回结果
return dp[word1.length()][word2.length()];
}
}8. 不同的二叉搜索树
问题描述
给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？
示例:
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
1 3 3 2 1 \ / / / \
3 2 1 1 3 2 / / \
2 1 2 3
算法思路
这个问题可以用一个一维数组dp来表示n个节点组成的二叉搜索树的个数，状态转移方程为dp [i] = sum (dp [j-1] * dp [i-j])，其中j是从1到i的所有位置。也就是说，对于每个位置i，我们要遍历它之前的所有位置j，把j作为根节点，那么左子树有j-1个节点，右子树有i-j个节点，左右子树的组合数就是dp [j-1] * dp [i-j]，然后把所有的组合数加起来就是dp [i]。最后我们返回dp [n]即可。
状态定义
dp [i]：表示i个节点组成的二叉搜索树的个数
状态转移方程
dp [i] = sum (dp [j-1] * dp [i-j])，其中j是从1到i的所有位置
Java代码实现
class Solution {
public int numTrees(int n) {
// 边界条件判断
if (n < 0) {
return 0;
}
// 定义状态数组
int[] dp = new int[n + 1];
// 初始化状态数组，0个节点和1个节点的情况都只有一种
dp[0] = 1;
dp[1] = 1;
// 遍历数组，根据状态转移方程更新dp数组
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
// 把每个位置作为根节点，计算左右子树的组合数，并累加到dp[i]
dp[i] += dp[j - 1] * dp[i - j];
}
}
// 返回结果
return dp[n];
}
}
9. 矩阵链乘法
问题描述
给定一个矩阵序列，确定最佳的矩阵相乘顺序。假设矩阵A[i]的维度为p[i-1]*p[i], 共有n个矩阵相乘。
示例：
输入：p[] = {40, 20, 30, 10, 30}
输出：26000
解释：
有4个矩阵A[1], A[2], A[3], A[4], 维度分别为4020,2030,3010,1030.
如果按照(A[1]A[2])(A[3]*A[4])的顺序相乘，则需要26000次标量乘法。
如果按照(A[1](A[2](A[3]*A[4])))的顺序相乘，则需要45000次标量乘法。
如果按照((A[1]*A[2])*A[3])*A[4]的顺序相乘，则需要30000次标量乘法。
所以最佳的相乘顺序是(A[1]A[2])(A[3]*A[4])。
算法思路
这个问题可以用一个二维数组dp来表示从第i个矩阵到第j个矩阵相乘所需的最少标量乘法次数，状态转移方程为dp [i] [j] = min (dp [i] [k] + dp [k+1] [j] + p[i-1]*p[k]*p[j])，其中k是从i到j-1的所有位置。也就是说，对于每个位置i和j，我们要遍历它们之间的所有位置k，把k作为分割点，那么左边有i到k个矩阵相乘，右边有k+1到j个矩阵相乘，再加上最后合并两边的结果所需的乘法次数，就是dp [i] [j]。我们要选择其中能使得dp [i] [j]最小的那个分割点k。最后我们返回dp [1] [n]即可。
状态定义
dp [i] [j]：表示从第i个矩阵到第j个矩阵相乘所需的最少标量乘法次数
状态转移方程
dp [i] [j] = min (dp [i] [k] + dp [k+1] [j] + p[i-1]*p[k]*p[j])，其中k是从i到j-1的所有位置
Java代码实现
class Solution {
public int matrixChainOrder(int[] p) {
// 边界条件判断
if (p == null || p.length == 0) {
return 0;
}
// 定义状态数组
int[][] dp = new int[p.length][p.length];
// 初始化状态数组，对角线上的元素为0，表示单个矩阵不需要乘法
for (int i = 0; i < p.length; i++) {
dp[i][i] = 0;
}
// 遍历数组，根据状态转移方程更新dp数组
// 注意要从下往上遍历，因为要用到下面的状态
for (int i = p.length - 2; i >= 0; i--) {
for (int j = i + 1; j < p.length; j++) {
// 定义一个临时变量记录最小值
int min = Integer.MAX_VALUE;
for (int k = i; k < j; k++) {
// 把每个位置作为分割点，计算左右两边的乘法次数，并累加到min
min = Math.min(min, dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j]);
}
// 更新当前位置的最小乘法次数
dp[i][j] = min;
}
}
// 返回结果
return dp[1][p.length - 1];
}
}
10. 0-1背包问题
问题描述
给定一组物品，每种物品都有自己的重量和价值，在限定的总重量内，我们如何选择，才能使得物品的总价值最大。
示例：
输入：n = 3, W = 4, wt[] = {2, 1, 3}, val[] = {4, 2, 3}
输出：6
解释：
选择第一件和第三件物品，总重量是2+3=5小于等于W=4，总价值是4+3=7。
选择第一件和第二件物品，总重量是2+1=3小于等于W=4，总价值是4+2=6。
选择第二件和第三件物品，总重量是1+3=4等于W=4，总价值是2+3=5。
所以最大价值是6。
算法思路
这个问题可以用一个二维数组dp来表示前i个物品在容量为w时能装下的最大价值，状态转移方程为dp [i] [w] = max (dp [i-1] [w], dp [i-1] [w-wt[i]] + val[i])。也就
是说，对于每个物品i和每个容量w，我们要判断是选择这个物品还是不选择这个物品，如果选择这个物品，那么就要在前i-1个物品中找到容量为w-wt[i]时的最大价值，并加上当前物品的价值，如果不选择这个物品，那么就要在前i-1个物品中找到容量为w时的最大价值。我们要选择其中能使得dp [i] [w]最大的那种情况。最后我们返回dp [n] [W]即可，其中n是物品的数量，W是背包的容量。
状态定义
dp [i] [w]：表示前i个物品在容量为w时能装下的最大价值
状态转移方程
dp [i] [w] = max (dp [i-1] [w], dp [i-1] [w-wt[i]] + val[i])
Java代码实现
class Solution {
public int knapsack(int W, int N, int[] weights, int[] values) {
// 边界条件判断
if (W <= 0 || N <= 0 || weights == null || values == null || weights.length == 0 || values.length == 0) {
return 0;
}
// 定义状态数组
int[][] dp = new int[N + 1][W + 1];
// 遍历数组，根据状态转移方程更新dp数组
for (int i = 1; i <= N; i++) {
for (int w = 1; w <= W; w++) {
if (weights[i - 1] <= w) {
// 如果当前物品的重量小于等于当前容量，说明可以选择这个物品
// 那么就要比较选择这个物品和不选择这个物品两种情况下的最大价值
dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
} else {
// 如果当前物品的重量大于当前容量，说明不能选择这个物品
// 那么就只能沿用前一个物品在当前容量下的最大价值
dp[i][w] = dp[i - 1][w];
}
}
}
// 返回结果
return dp[N][W];
}
}