动态规划：进阶算法思维

# 1. 动态规划基础概念
- 1.1 什么是动态规划
- 1.2 动态规划的原理和特点
- 1.3 动态规划与递归、贪心算法的区别

# 2. 动态规划解题思路

- 2.1 自底向上的动态规划解题法
- 2.2 利用状态转移方程解决子问题
- 2.3 实例分析：斐波那契数列和背包问题的动态规划解法

在第二章中，我们将深入探讨动态规划的解题思路，包括自底向上的动态规划解题法以及利用状态转移方程解决子问题的方法。我们也会通过实例分析，展示斐波那契数列和背包问题的动态规划解法，帮助读者更好地理解动态规划算法的实际运用。

# 3. 常见动态规划变形问题

动态规划常见的变形问题包括最长递增子序列问题、编辑距离问题和股票交易问题，下面将逐一介绍它们的特点和解题思路。

#### 3.1 最长递增子序列问题

最长递增子序列问题是指在一个给定的序列中，找到一个最长的子序列，使得这个子序列是递增的。例如，对于序列 [10, 9, 2, 5, 3, 7, 101, 18]，最长递增子序列为 [2, 3, 7, 101]，长度为 4。

动态规划解法思路：
- 定义状态：dp[i] 表示以第 i 个元素为结尾的最长递增子序列的长度。
- 状态转移方程：dp[i] = max(dp[i], dp[j] + 1)，其中 0 <= j < i，且 nums[j] < nums[i]。

Python代码示例：

def lengthOfLIS(nums):
    if not nums:
        return 0
    n = len(nums)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

# 测试示例
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(lengthOfLIS(nums))  # Output: 4

总结：最长递增子序列问题可以通过动态规划的方式求解，时间复杂度为 O(n^2)。利用动态规划，可以在遍历数组的过程中不断更新状态，最终得到最优解。

#### 3.2 编辑距离问题

编辑距离问题是指给定两个单词 word1 和 word2，通过插入、删除、替换操作，将 word1 转换为 word2 所需的最少操作次数。

动态规划解法思路：
- 定义状态：dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作次数。
- 状态转移方程：
- 当 word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]；
- 否则，dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1。

Java代码示例：

public int minDistance(String word1, String word2) {
    int m = word1.length();
    int n = word2.length();
    int[][] dp = new int[m+1][n+1];
    for (int i = 0; i <= m; i++) {
        dp[i][0] = i;
    }
    for (int j = 0; j <= n; j++) {
        dp[0][j] = j;
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i-1) == word2.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i][j-1], dp[i-1][j])) + 1;
            }
        }
    }
    return dp[m][n];
}

// 测试示例
String word1 = "horse";
String word2 = "ros";
System.out.println(minDistance(word1, word2));  // Output: 3

总结：编辑距离问题可以通过动态规划的方式求解，时间复杂度为 O(mn)，其中 m 和 n 分别为两个单词的长度。动态规划的优势在于可以利用之前计算过的状态，减少重复计算，提高效率。

#### 3.3 股票交易问题

股票交易问题是指给定一个数组 prices，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。设计一个算法来计算你所能获得的最大利润。可以多次完成交易（买入和卖出一支股票多次）。

动态规划解法思路：
- 定义状态：
- dp[i][0] 表示第 i 天不持有股票的最大利润；
- dp[i][1] 表示第 i 天