golang-cookbook

Appearance

不同维度的动态规划问题 ​

动态规划（Dynamic Programming，简称 DP）是一种将复杂问题分解成较小的子问题的算法设计方法。不同维度的动态规划表通常用来表示不同的子问题状态，状态的维度数目决定了动态规划表的维度。

1. 一维动态规划 (1D DP) ​

一维动态规划通常用于那些状态仅依赖于单一变量的情况。可以使用一维数组（或列表）来存储子问题的解。

示例：斐波那契数列 ​

斐波那契数列是一个经典的动态规划问题，其状态仅依赖于前两个状态，因此可以通过一维 DP 数组来求解。

状态定义：

  • dp[i] 表示第 i 个斐波那契数。

状态转移方程：

  • dp[i] = dp[i-1] + dp[i-2] （i >= 2）

代码示例：

go
func fib(n int) int {
    if n <= 1 {
        return n
    }
    
    dp := make([]int, n+1)
    dp[0], dp[1] = 0, 1
    
    for i := 2; i <= n; i++ {
        dp[i] = dp[i-1] + dp[i-2]
    }
    
    return dp[n]
}

2. 二维动态规划 (2D DP) ​

二维动态规划常用于那些状态依赖于两个变量的情况。可以使用二维数组来表示状态转移。例如，常见的 最长公共子序列（LCS） 问题、背包问题 等。

示例：最长公共子序列 (LCS) ​

LCS 问题可以通过二维动态规划来解决，其中 dp[i][j] 表示字符串 s1[0..i-1] 和 s2[0..j-1] 的最长公共子序列的长度。

状态定义：

  • dp[i][j] 表示 s1[0..i-1] 和 s2[0..j-1] 的最长公共子序列的长度。

状态转移方程：

  • 如果 s1[i-1] == s2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1；
  • 否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

代码示例：

go
func longestCommonSubsequence(s1 string, s2 string) int {
    m, n := len(s1), len(s2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if s1[i-1] == s2[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]
}

3. 三维动态规划 (3D DP) ​

三维动态规划通常用于那些状态依赖于三个变量的情况。例如，三维背包问题，或者 序列的某些条件的组合。

示例：三维背包问题 ​

在三维背包问题中，状态不仅依赖于物品的数量，还依赖于物品的种类和重量。

状态定义：

  • dp[i][j][k] 表示在考虑前 i 个物品，背包容量为 j，种类为 k 的情况下能够得到的最大价值。

状态转移方程：

  • dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-weights[i]][k-1] + values[i])

4. 四维及更高维动态规划 ​

四维动态规划及更高维动态规划的场景较为少见，但在某些复杂问题中，可能需要依赖多个变量来描述子问题的解。例如，多维背包问题（考虑多个维度的限制），或 最小成本流 问题。

示例：四维背包问题 ​

假设我们有一个四维背包问题，背包不仅有重量限制，还有其他多个维度的限制（比如物品种类，体积等）。

状态定义：

  • dp[i][j][k][l] 表示考虑前 i 个物品，在限制条件 (j, k, l) 下的最优解。

复杂性 ​

随着维度的增加，动态规划表的大小会急剧增大。四维或更高维的动态规划需要考虑状态转移的效率和表的存储复杂性。实际中，通常会优化空间复杂度，可能通过滚动数组或压缩维度来减少空间消耗。

5. 状态压缩（降维） ​

有时，状态转移只依赖于较少的状态，因此不需要存储完整的 DP 表。例如，在很多问题中，我们的当前状态只依赖于前一行或前一个维度的状态，此时可以通过 状态压缩 技术将二维或三维 DP 降维到一维数组。这样可以有效节省空间。

示例：背包问题的空间优化 ​

假设我们在解决 0/1 背包问题时，当前状态只依赖于前一行的数据。因此，我们可以使用一维数组而不是二维数组来优化空间。

go
func knapsack(weights []int, values []int, capacity int) int {
    dp := make([]int, capacity+1)
    
    for i := 0; i < len(weights); i++ {
        for j := capacity; j >= weights[i]; j-- {
            dp[j] = max(dp[j], dp[j-weights[i]] + values[i])
        }
    }
    
    return dp[capacity]
}

总结 ​

  1. 一维动态规划：适用于只依赖一个变量的状态问题，通常使用一维数组存储结果。
  2. 二维动态规划：适用于依赖两个变量的状态问题，通常使用二维数组存储结果。常见问题包括最长公共子序列、最小路径和等。
  3. 三维及更高维动态规划：适用于更复杂的状态问题，例如多维背包问题、复杂的路径问题等。
  4. 状态压缩：有时我们可以通过优化空间复杂度，将高维的 DP 表压缩成一维，从而节省存储空间。

动态规划的维度取决于问题的复杂性，较高维度的动态规划能更精确地表示复杂的状态转移，但同时也需要考虑到空间和时间的优化。