动态规划问题

动态规划几个场景问题和理解

动态规划问题的本质

动态规划（Dynamic Programming, DP）是一种通过将复杂问题分解为更小的子问题来解决优化问题的算法策略。它在计算机科学中应用广泛，尤其是在需要寻找最优解的场景中。动态规划的核心思想是通过存储子问题的解来避免重复计算，从而提高效率。以下将详细讲解动态规划的本质、在计算机体系架构中的运行方式、状态转移的本质，并通过具体例子帮助理解，最后从底层原理彻底阐释。

动态规划的本质是什么

动态规划的本质在于通过存储子问题的解来避免重复计算，从而高效地解决复杂问题。它基于两个关键特性：

1. 最优子结构：一个问题的最优解可以通过其子问题的最优解来构建。例如，要计算第 ( n ) 个斐波那契数，可以通过第 ( n-1 ) 和第 ( n-2 ) 个数的最优解（即它们的值）来得到。
2. 重叠子问题：在求解过程中，相同的子问题会被多次用到。如果不存储这些子问题的解，而是每次都重新计算，会导致效率低下。动态规划通过存储这些解来优化性能。

简单来说，动态规划的核心是利用内存换时间，通过记录子问题的结果，避免重复劳动，最终高效地解决原问题。

在计算机体系架构中，动态规划是如何运行的

在计算机体系架构中，动态规划通常以一种结构化的方式运行，依赖内存和计算的结合。它的运行过程可以分为以下几个步骤：

1. 状态定义
   定义一个状态数组（或矩阵），其中每个元素代表一个子问题的解。例如，在斐波那契数列中，( dp[i] ) 表示第 ( i ) 个斐波那契数；在背包问题中，( dp[i][w] ) 表示前 ( i ) 个物品在容量 ( w ) 下的最大价值。

2. 状态转移
   通过状态转移方程，从已知的子问题解逐步推导出更大的子问题解。状态转移方程描述了子问题之间的关系。例如，在斐波那契数列中，( dp[i] = dp[i-1] + dp[i-2] )。

3. 边界条件
   设置初始状态，即最小的子问题的解。例如，斐波那契数列的 ( dp[1] = 1 )，( dp[2] = 1 )。

4. 计算顺序
   按照一定的顺序（通常是自底向上）填充状态数组。自底向上的方法从最小子问题开始，逐步计算到最终问题，避免了递归的开销。

5. 结果获取
   从状态数组中直接读取最终问题的解。例如，( dp[n] ) 就是第 ( n ) 个斐波那契数。

在计算机中，动态规划利用内存（如数组或哈希表）存储中间结果，CPU 按照状态转移方程逐步更新这些状态，最终得到答案。这种方法充分利用了计算机的存储和计算能力。

状态转移的过程本质是什么

状态转移的本质是描述子问题之间的关系，即如何从一个或多个已知子问题的解推导出另一个子问题的解。状态转移方程是动态规划的核心，它定义了从当前状态到下一状态的规则。

• 形式化表示：状态转移通常是一个数学公式或逻辑表达式。例如，( dp[i] = dp[i-1] + dp[i-2] ) 表示第 ( i ) 个状态依赖于前两个状态。
• 决策过程：在优化问题中，状态转移往往涉及选择。例如，在背包问题中，状态转移需要决定是否放入某个物品，取价值最大的一种情况。

状态转移的意义在于，它将一个大问题分解为多个小问题，并通过递推的方式逐步解决，最终连接到原问题的解。

用具体例子理解动态规划

以下通过两个经典例子详细说明动态规划的实现过程。

例子 1：斐波那契数列

问题描述：计算第 ( n ) 个斐波那契数。斐波那契数列的前两个数为 1，后续每个数是前两个数的和。即：

• ( F(1) = 1 )
• ( F(2) = 1 )
• ( F(n) = F(n-1) + F(n-2) ) 对于 ( n > 2 )

动态规划解法：

1. 状态定义
   定义 ( dp[i] ) 表示第 ( i ) 个斐波那契数。

2. 状态转移方程
   ( dp[i] = dp[i-1] + dp[i-2] )
   即第 ( i ) 个数是前两个数的和。

3. 边界条件
   ( dp[1] = 1 )
   ( dp[2] = 1 )

4. 计算顺序
   从 ( i = 3 ) 到 ( n )，依次计算每个 ( dp[i] )。
   例如：

   • ( dp[3] = dp[2] + dp[1] = 1 + 1 = 2 )
   • ( dp[4] = dp[3] + dp[2] = 2 + 1 = 3 )
   • ( dp[5] = dp[4] + dp[3] = 3 + 2 = 5 )

5. 结果获取
   ( dp[n] ) 即为第 ( n ) 个斐波那契数。

代码示例（Go）：

package main

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

例子 2：0-1 背包问题

问题描述：
给定一个容量为 ( W ) 的背包和 ( n ) 个物品，每个物品有重量 ( w_i ) 和价值 ( v_i )。求解如何选择物品放入背包，使得总价值最大，且总重量不超过 ( W )。
例如：( W = 4 )，物品信息如下：

• 物品 1：重量 ( w_1 = 2 )，价值 ( v_1 = 3 )
• 物品 2：重量 ( w_2 = 3 )，价值 ( v_2 = 4 )
• 物品 3：重量 ( w_3 = 1 )，价值 ( v_3 = 2 )

动态规划解法：

1. 状态定义
   ( dp[i][w] ) 表示前 ( i ) 个物品在背包容量为 ( w ) 时的最大价值。

2. 状态转移方程
   对于第 ( i ) 个物品：

   • 不放入背包：$dp[i][w] = dp[i-1][w]$
   • 放入背包（如果 $w \geq w_i$）：$dp[i][w] = dp[i-1][w - w_i] + v_i$
     因此：
     $dp[i][w] = \max(dp[i-1][w], dp[i-1][w - w_i] + v_i)$ 如果 $w \geq w_i$
     $dp[i][w] = dp[i-1][w]$ 如果 $w < w_i$

3. 边界条件

   • $dp[0][w] = 0$（无物品时价值为 0）
   • $dp[i][0] = 0$（容量为 0 时价值为 0）

4. 计算顺序
   从 $i = 1$ 到 $n$，对于每个 $i$，从 $w = 0$ 到 $W$，填充 $dp$ 表。
   示例计算（$n = 3, W = 4$）：

   • $dp[1][4] = \max(dp[0][4], dp[0][4-2] + 3) = \max(0, 0 + 3) = 3$（放入物品 1）
   • $dp[2][4] = \max(dp[1][4], dp[1][4-3] + 4) = \max(3, 0 + 4) = 4$（放入物品 2）
   • $dp[3][4] = \max(dp[2][4], dp[2][4-1] + 2) = \max(4, 3 + 2) = 5$（放入物品 3）

5. 结果获取
   $dp[3][4] = 5$ 是最终答案。

代码示例：

func knapsack(W int, weights []int, values []int, n int) int {
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, W+1)
	}

	for i := 1; i <= n; i++ {
		for w := 0; w <= W; w++ {
			if w >= weights[i-1] {
				dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]]+values[i-1])
			} else {
				dp[i][w] = dp[i-1][w]
			}
		}
	}
	return dp[n][W]
}

动态规划的底层原理

动态规划的底层原理涉及几个关键概念：

1. 记忆化
   通过存储子问题的解（如数组或哈希表），避免重复计算。例如，在斐波那契数列中，如果不使用 ( dp ) 数组，递归方法会重复计算 ( F(n-1) ) 和 ( F(n-2) )，时间复杂度为指数级 ( O(2^n) )。而动态规划将其优化为 ( O(n) )。

2. 递归与迭代
   动态规划有两种实现方式：

   • 自顶向下：递归加记忆化，先分解问题，再计算子问题。
   • 自底向上：迭代方式，从最小子问题开始递推到最终解。通常自底向上更高效，因为它避免了递归的栈开销。

3. 空间优化
   在某些问题中，可以通过减少存储来优化空间。例如，在斐波那契数列中，只需保存前两个状态，而无需整个 ( dp ) 数组：

   def fibonacci_optimized(n):
       if n <= 1:
           return n
       a, b = 1, 1
       for _ in range(3, n + 1):
           a, b = b, a + b
       return b
   

4. 时间复杂度优化
   动态规划常将指数时间复杂度优化为多项式时间。例如，背包问题若用暴力枚举，复杂度为 ( O(2^n) )，而动态规划将其优化为 ( O(nW) )。

总结

动态规划是一种通过分解问题为子问题并存储子问题解来避免重复计算的算法策略。其本质是利用最优子结构和重叠子问题，通过状态数组和状态转移方程在计算机中高效运行。状态转移描述了子问题之间的递推关系，是动态规划的核心。通过斐波那契数列和背包问题的例子，我们看到动态规划如何将复杂问题转化为简单的递推计算。从底层原理看，动态规划通过记忆化、迭代和空间优化，充分利用计算机的内存和计算能力，显著提升效率。

221. 最大正方形

问题描述

在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。

示例输入：

matrix = [
    ["1","0","1","0","0"],
    ["1","0","1","1","1"],
    ["1","1","1","1","1"],
    ["1","0","0","1","0"]
]

示例输出： 4

解题思路

这道题目要求在二维矩阵中找到只包含 ‘1’ 的最大正方形，并返回其面积。使用动态规划（DP）来解决问题：

状态定义

设 dp[i][j] 表示以位置 (i, j) 为右下角的、只包含 ‘1’ 的最大正方形的边长。

状态转移方程

• 如果 matrix[i][j] 为 ‘1’：

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

• 如果 matrix[i][j] 为 ‘0’，则 dp[i][j] = 0

边界条件

• 第一行和第一列由于没有上面或左边的元素，所以当 matrix[i][j] 为 ‘1’ 时，dp[i][j] = 1，否则为 0。

结果计算

在遍历过程中维护一个变量 maxSide 用来记录遇到的最大正方形边长，最后返回 maxSide * maxSide 作为面积。

举个例子

1  0  1
1  1  1
1  1  1

dp[0][0] = 1
dp[1][1] = 1 // 因为dp[0][1] = 0 
dp[2][2] = 2 // dp[1][1] = 1 dp[2][1] = 1 dp[1][2] = 1

代码实现

package main

import (
    "fmt"
)

func maximalSquare(matrix [][]byte) int {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return 0
    }
    
    m, n := len(matrix), len(matrix[0])
    // 创建dp二维数组，初始化为0
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    
    maxSide := 0
    
    // 遍历矩阵
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if matrix[i][j] == '1' {
                if i == 0 || j == 0 {
                    dp[i][j] = 1
                } else {
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                }
                if dp[i][j] > maxSide {
                    maxSide = dp[i][j]
                }
            } else {
                dp[i][j] = 0
            }
        }
    }
    return maxSide * maxSide
}

复杂度分析

• 时间复杂度： O(m * n)，需要遍历整个矩阵的每个元素
• 空间复杂度： O(m * n)，使用了一个大小为 m×n 的 dp 数组

72. 编辑距离

解题思路

1. 定义 DP 状态

   • 设 dp[i][j] 表示将 word1[0:i] 变成 word2[0:j] 需要的最少操作数。
   • 其中 word1[0:i] 表示 word1 的前 i 个字符，word2[0:j] 表示 word2 的前 j 个字符。

2. 状态转移方程
   对于 word1[i-1] 和 word2[j-1]，有三种情况：

   • 如果 word1[i-1] == word2[j-1]，则不需要操作：
     [ dp[i][j] = dp[i-1][j-1] ]
   • 否则，需要进行以下三种操作之一（取最小值）：
     • 插入一个字符（等价于 word1[0:i] 需要变成 word2[0:j-1]，然后再加上 word2[j-1]）：
       [ dp[i][j] = dp[i][j-1] + 1 ]
     • 删除一个字符（等价于 word1[0:i-1] 需要变成 word2[0:j]，然后删除 word1[i-1]）：
       [ dp[i][j] = dp[i-1][j] + 1 ]
     • 替换一个字符（等价于 word1[0:i-1] 需要变成 word2[0:j-1]，然后把 word1[i-1] 替换成 word2[j-1]）：
       [ dp[i][j] = dp[i-1][j-1] + 1 ]
     • 最终转移方程为： [ dp[i][j] = \min(dp[i-1][j-1] + 1, dp[i][j-1] + 1, dp[i-1][j] + 1) ]

3. 初始化

   • dp[0][j] = j：如果 word1 为空，则需要插入 j 个字符。
   • dp[i][0] = i：如果 word2 为空，则需要删除 i 个字符。

举个例子

1. 插入操作

场景描述：
假设 word1 = “a”，word2 = “ab”。
目标：把 “a” 变成 “ab”。

思路：

• 考察 dp[1][2]，即将 word1 的前 1 个字符 (“a”) 转换为 word2 的前 2 个字符 (“ab”)。
• 插入操作的含义是：如果我们已经把 “a” 变成了 “a”（即 dp[1][1]），那么再在末尾插入 word2 的第 2 个字符 ‘b’，总操作数就增加 1。
• 因此：
  [ dp[1][2] = dp[1][1] + 1 ]

具体过程：

• dp[1][1] 表示 “a” → “a”，显然不需要操作，所以 dp[1][1] = 0。
• 然后 dp[1][2] = 0 + 1 = 1。

2. 删除操作

场景描述：
假设 word1 = “ab”，word2 = “a”。
目标：把 “ab” 变成 “a”。

思路：

• 考察 dp[2][1]，即将 word1 的前 2 个字符 (“ab”) 转换为 word2 的前 1 个字符 (“a”)。
• 删除操作的含义是：如果我们已经把 “a”（word1 的前 1 个字符）转换为 “a”（word2 的前 1 个字符），那么在 word1 的 “ab” 中，多出来的那个字符 ‘b’ 就需要删除，操作数加 1。
• 因此：
  [ dp[2][1] = dp[1][1] + 1 ]

具体过程：

• dp[1][1] 表示 “a” → “a”，结果为 0。
• 然后 dp[2][1] = 0 + 1 = 1。

3. 替换操作

场景描述：
假设 word1 = “cat”，word2 = “cut”。
目标：把 “cat” 变成 “cut”。

思路：

• 对比两个字符串的每个位置：
  • 第 1 个字符：‘c’ 与 ‘c’ 相同，无需操作。
  • 第 2 个字符：‘a’ 与 ‘u’ 不同，需要替换。
  • 第 3 个字符：’t’ 与 ’t’ 相同，无需操作。
• 当我们考虑 dp[2][2] 时，代表将 word1 的前 2 个字符 (“ca”) 转换为 word2 的前 2 个字符 (“cu”)。
• 因为 ‘a’ 与 ‘u’ 不同，我们可以选择用替换操作：
  [ dp[2][2] = dp[1][1] + 1 ] 其中 dp[1][1] 表示 “c”→“c”（结果为 0），替换操作加 1，所以 dp[2][2] = 0 + 1 = 1。
• 后续再处理第 3 个字符时，因为两者都是 ’t’，所以 dp[3][3] 就等于 dp[2][2]，即 1。

具体过程：

• dp[1][1] = 0 （“c”→“c”）
• dp[2][2] = 0 + 1 = 1 （将 “ca”→“cu”，这里替换了 ‘a’ 为 ‘u’）
• dp[3][3] = dp[2][2] = 1 （“cat”→“cut”，第 3 个字符相同）

Golang 代码

package main

import (
	"fmt"
)

// minDistance 计算最小编辑距离
func minDistance(word1 string, word2 string) int {
	m, n := len(word1), len(word2)
	dp := make([][]int, m+1)

	// 初始化二维数组
	for i := range dp {
		dp[i] = make([]int, n+1)
	}

	// 初始化第一行和第一列
	for i := 0; i <= m; i++ {
		dp[i][0] = i
	}
	for j := 0; j <= n; j++ {
		dp[0][j] = j
	}

	// 动态规划填表
	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][j-1]+1, dp[i-1][j]+1)
			}
		}
	}

	// 返回最终结果
	return dp[m][n]
}

复杂度分析

• 时间复杂度：O(m × n)，其中 m 和 n 分别是 word1 和 word2 的长度。我们需要遍历 m × n 个状态，每个状态的计算时间是 O(1)。
• 空间复杂度：O(m × n)，由于使用了 m × n 的二维 dp 数组。