动态规划（Dynamic Programming，简称 DP）

动态规划是一种优化技术，用来解决具有重叠子问题和最优子结构性质的问题。它通过将大问题分解成小的子问题，保存每个子问题的解来避免重复计算，从而降低计算复杂度。

基本思路：

1. 问题分解：将大问题分解成子问题，子问题之间相互依赖，且有重叠的计算。
2. 状态定义：明确子问题的解如何表示，一般定义一个数组或者表格来存储子问题的解。
3. 状态转移方程：找到不同子问题之间的关系，用方程表达子问题之间的依赖关系。
4. 边界条件：初始化子问题的基础解，即最小子问题的解。

动态规划的两种实现方式：

• 自顶向下（Top-Down）：通过递归进行求解，通常结合记忆化搜索（Memoization）来存储已经计算过的子问题结果，避免重复计算。
• 自底向上（Bottom-Up）：通过迭代的方式，从最小子问题开始逐步推导到最终问题的解。

二维动态规划（2D DP）

二维动态规划是动态规划的一种扩展，它用于求解那些涉及两个变量的最优子问题。例如，处理两维数据结构（如二维矩阵、网格、字符串对比等）的问题时，常常使用二维动态规划。

常见问题：

• 最长公共子序列（Longest Common Subsequence, LCS）：给定两个字符串，求它们的最长公共子序列的长度。
• 背包问题：在二维背包问题中，一个背包不仅考虑物品的重量，还有容量。
• 编辑距离问题（Levenshtein Distance）：计算两个字符串之间最少的编辑操作（插入、删除、替换）次数。

2D DP的基本思想：

在二维动态规划中，我们常常使用一个二维数组（dp[i][j]）来存储每个子问题的解。例如，假设有两个字符串 word1 和 word2，我们用二维数组 dp[i][j] 表示 word1[0:i] 和 word2[0:j] 之间的编辑距离。每个子问题的解通过已有的子问题逐步推导出来。

2D DP 示例 - 编辑距离

假设我们有两个字符串 word1 和 word2，我们想找出它们的编辑距离（最少的编辑操作数：插入、删除、替换）。我们可以用一个二维 DP 数组 dp[i][j] 来表示 word1[0:i] 转换成 word2[0:j] 所需的最少操作数。

状态转移方程：

1. 如果 word1[i-1] == word2[j-1]：不需要操作，dp[i][j] = dp[i-1][j-1]。
2. 如果 word1[i-1] != word2[j-1]：我们可以进行插入、删除或替换，转移方程为：

   dp[i][j] = min(dp[i-1][j-1] + 1, dp[i-1][j] + 1, dp[i][j-1] + 1)

初始化条件：

• dp[0][j] = j，表示将空字符串转换成 word2[0:j] 的操作数是 j（即插入 j 个字符）。
• dp[i][0] = i，表示将 word1[0:i] 转换为空字符串的操作数是 i（即删除 i 个字符）。

代码实现：

func minDistance(word1 string, word2 string) int {
    m, n := len(word1), len(word2)

    // 创建 dp 数组，dp[i][j] 表示 word1[0:i] 转换为 word2[0:j] 的最小操作数
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    // 初始化 dp 数组
    for i := 0; i <= m; i++ {
        dp[i][0] = i  // 将 word1[0:i] 转换为空字符串的操作数为 i（删除操作）
    }
    for j := 0; j <= n; j++ {
        dp[0][j] = j  // 将空字符串转换为 word2[0:j] 的操作数为 j（插入操作）
    }

    // 填充 dp 数组
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if word1[i-1] == word2[j-1] {
                dp[i][j] = dp[i-1][j-1]  // 如果字符相同，不需要操作
            } else {
                dp[i][j] = min(
                    dp[i-1][j-1] + 1, // 替换操作
                    dp[i-1][j] + 1,   // 删除操作
                    dp[i][j-1] + 1,   // 插入操作
                )
            }
        }
    }

    return dp[m][n]  // 返回将 word1 转换为 word2 的最小操作数
}

// 辅助函数：返回三个数中的最小值
func min(a, b, c int) int {
    if a < b {
        if a < c {
            return a
        }
        return c
    }
    if b < c {
        return b
    }
    return c
}

2D DP 示例 - 最长公共子序列

另一个常见的二维动态规划问题是求解 最长公共子序列。给定两个字符串 text1 和 text2，我们想要找出它们的最长公共子序列的长度。

状态转移方程：

1. 如果 text1[i-1] == text2[j-1]：dp[i][j] = dp[i-1][j-1] + 1，因为我们找到了一个公共字符。
2. 如果 text1[i-1] != text2[j-1]：dp[i][j] = max(dp[i-1][j], dp[i][j-1])，表示我们要么忽略 text1[i-1]，要么忽略 text2[j-1]。

代码实现：

func longestCommonSubsequence(text1 string, text2 string) int {
    m, n := len(text1), len(text2)
    
    // 创建 dp 数组，dp[i][j] 表示 text1[0:i] 和 text2[0:j] 的最长公共子序列长度
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    // 填充 dp 数组
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if text1[i-1] == text2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1  // 如果字符相同，最长公共子序列长度加1
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])  // 否则取最大值
            }
        }
    }

    return dp[m][n]  // 返回最长公共子序列的长度
}

// 辅助函数：返回两个数中的最大值
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

总结：

1. 二维动态规划是处理涉及两维数据的优化问题的一种方法，常用于二维数组或矩阵问题（如编辑距离、最长公共子序列等）。
2. 状态定义是解决问题的关键，需要清晰地定义出每个子问题的解如何表示。
3. 状态转移方程通过分析子问题之间的关系，决定如何通过已有的解来得到当前问题的解。