下面结合常见的动态规划问题，详细分析动态规划解题的四个步骤。
1. 定义状态
定义状态是动态规划解题的基础，它要求你明确问题的状态表示以及每个状态所代表的含义。通常，状态是问题的一个子问题，通过对状态的定义，我们能将原问题拆解为一系列子问题。
示例：最长递增子序列（LIS）问题
给定一个无序的整数数组，找到其中最长递增子序列的长度。
- 状态定义：设
dp[i]表示以第i个元素结尾的最长递增子序列的长度。这里状态的含义是，只考虑数组前i个元素，并且要求子序列必须以第i个元素结尾时的最长递增子序列长度。
2. 确定状态转移方程
状态转移方程描述了状态之间的递推关系，它是动态规划的核心。通过状态转移方程，我们可以从已知的子问题解推导出未知的子问题解。
示例：最长递增子序列（LIS）问题
对于dp[i]，我们需要遍历数组中i之前的所有元素j（0 <= j < i），如果nums[j] < nums[i]，说明可以将第i个元素添加到以第j个元素结尾的递增子序列后面，从而形成一个更长的递增子序列。
- 状态转移方程：
dp[i] = max(dp[j] + 1, dp[i])，其中0 <= j < i且nums[j] < nums[i]。这个方程的含义是，对于每个满足条件的j，计算dp[j] + 1（即在以第j个元素结尾的最长递增子序列后面加上第i个元素），并取这些值中的最大值作为dp[i]。
3. 初始化状态
初始化状态是为了确定问题的边界条件，即一些最简单的子问题的解。这些初始状态将作为后续递推的基础。
示例：最长递增子序列（LIS）问题
由于每个元素自身都可以构成一个长度为 1 的递增子序列，所以初始时，我们将dp数组的每个元素都初始化为 1。
- 初始化代码：
int[] dp = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
dp[i] = 1;
}
4. 计算最终结果
在完成状态定义、状态转移方程的确定和状态的初始化后，我们可以根据状态转移方程逐步计算出所有子问题的解，最终得到原问题的解。
示例：最长递增子序列（LIS）问题
我们需要遍历数组，根据状态转移方程更新dp数组的值，最后在dp数组中找到最大值，即为最长递增子序列的长度。
- 计算最终结果的代码：
public class LongestIncreasingSubsequence {
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
int[] dp = new int[n];
// 初始化状态
for (int i = 0; i < n; i++) {
dp[i] = 1;
}
int maxLength = 1;
// 根据状态转移方程计算 dp 数组
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[j] + 1, dp[i]);
}
}
// 更新最长递增子序列的长度
maxLength = Math.max(maxLength, dp[i]);
}
return maxLength;
}
public static void main(String[] args) {
LongestIncreasingSubsequence lis = new LongestIncreasingSubsequence();
int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
int result = lis.lengthOfLIS(nums);
System.out.println("最长递增子序列的长度是: " + result);
}
}
复杂度分析
- 时间复杂度：由于使用了两层嵌套循环，时间复杂度为$O(n^2)$，其中
n是数组的长度。 - 空间复杂度：使用了一个长度为
n的数组dp来保存子问题的解，空间复杂度为$O(n)$。
通过以上四个步骤，我们可以使用动态规划解决最长递增子序列问题。对于其他动态规划问题，也可以按照类似的思路进行分析和求解。