动态规划
动态规划是一种通过将复杂问题分解为更小的子问题,并存储子问题的解以避免重复计算的优化技术。它特别适用于具有重叠子问题和最优子结构性质的问题。
核心:
- 状态: 动态规划中每个状态代表问题在某个阶段的部分解。
或者说,动态规划的核心,通过将问题分解,然后由初始最优解推到全局最优解。
- 状态转移方程: 通过状态转移方程,当前状态的值由之前的状态计算得到。
工作原理:
- 自底向上: 动态规划通常采用自底向上的方式,从最基本的子问题开始逐步解决,直到解决原问题。
这儿是迭代版本,即通过递推向上求解,例如背包问题的递推。
同样有递归版本,即通过递归将原问题逐步分解为小问题,有的地方会说从顶向下。个人认为,求解过程依然是从低向上。所以务必注意!!!
- 记忆化: 通过存储子问题的解,避免在后续计算中重复求解相同的子问题。
典型问题
最长公共子序列问题
给定两个字符串,找到它们最长 的公共子序列(LCS),即在不改变顺序的前提下,在两个字符串中都出现的最大子序列。
例如,输入字符串 X = "ABCBDAB"
和 Y = "BDCABA"
,其最长公共子序列为 "BDAB"
,长度为 4。
代码示例:
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size();
int n = text2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1[i - 1] == text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
};
在这个代码中,dp[i][j]
表示字符串 text1[0..i-1]
和 text2[0..j-1]
的最长公共子序列的长度。通过填充 dp
表,最终可以得到 text1
和 text2
的最长公共子序列长度。
爬楼梯问题
假设你正在爬楼梯。需要
n
阶你才能到达楼顶。每次你可以爬1
或2
个台阶。你有多少种不同的方法可以爬到楼顶?
这个问题可以看作一个斐波那契数列问题,因为到达第 n
阶的方法数等于到达第 n-1
阶和第 n-2
阶的方法数之和。
代码示例:
class Solution {
public:
int climbStairs(int n) {
if (n <= 2) return n;
int a = 1, b = 2;
for (int i = 3; i <= n; i++) {
int temp = a + b;
a = b;
b = temp;
}
return b;
}
};
在这个代码中,我们利用了滚动数组的思想,只需两个变量 a
和 b
来存储之前的两个状态,从而将空间复杂度从 O(n)
优化为 O(1)
。
动态规划的优化
动态规划的主要优化方向是空间复杂度和状态转移的优化。
- 空间优化: 对于某些问题,只需保留上一状态或几种状态的信息,可以通过减少维度来优化空间复杂度。
- 状态压缩: 有些问题可以通过“状态压缩”技术减少所需存储的状态,从而减少空间复杂度。
- 最优子结构和重叠子问题: 有些问题可以利用贪心算法或分治法进行进一步优化。