动态规划

动态规划（Dynamic Programming, DP）是一种算法设计技巧，它将一个复杂问题分解成若干个子问题，通过求解子问题来逐步求解原问题。动态规划通常用于求解最优化问题。解决动态规划问题的通用思路可以分为以下几个步骤：

定义状态：确定状态表示什么，每个状态需要包含哪些参数才能将问题描述完整。
状态转移方程：找出状态之间的关系，即如何从一个或多个较小的子问题的解得到当前问题的解。
初始化：确定边界条件，即最简单的子问题的解。
计算顺序：确定计算状态的顺序，以确保在计算一个状态时，所依赖的状态已经被计算。
答案重构（可选）：如果问题要求具体的解决方案，而不仅仅是解的值，可能需要从最终状态反向追溯以构造解决方案。
优化（可选）：对于空间复杂度，可以考虑状态压缩，只存储必要的状态。

下面是一个使用 Go 语言实现的动态规划问题的例子。我们将解决一个经典的问题：0-1 背包问题。在这个问题中，我们有一个背包和一些物品，每个物品都有一个重量和一个价值，我们需要选择一些物品放入背包中，使得背包中物品的总价值最大，同时不超过背包的最大承重。

package main

import (
	"fmt"
)

// 0-1背包问题
func knapsack(weights []int, values []int, W int) int {
	n := len(weights)
	// dp[i][w] 表示对于前i个物品，当前背包容量为w时的最大价值
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, W+1)
	}

	// 初始化已经在make的时候完成，所有值默认为0

	// 构建dp表
	for i := 1; i <= n; i++ {
		for w := 1; w <= W; w++ {
			if weights[i-1] <= w {
				// 可以选择放入第i个物品或不放入，取决于哪种选择价值更大
				dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]]+values[i-1])
			} else {
				// 当前背包容量无法放下第i个物品，只能选择不放入
				dp[i][w] = dp[i-1][w]
			}
		}
	}

	// 最大价值在dp[n][W]
	return dp[n][W]
}

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

func main() {
	weights := []int{1, 3, 4, 5} // 物品的重量
	values := []int{1, 4, 5, 7}  // 物品的价值
	W := 7                        // 背包的最大承重

	maxValue := knapsack(weights, values, W)
	fmt.Printf("The maximum value is %d\n", maxValue)
}

在这个例子中，我们定义了一个二维数组dp，其中dp[i][w]表示对于前i个物品，当前背包容量为w时的最大价值。我们通过比较放入和不放入当前物品的价值来填充这个表，并最终得到dp[n][W]，即所有物品和背包最大容量下的最大价值。

1. 斐波那契数列

斐波那契数列是动态规划中的经典入门问题。我们可以使用动态规划来避免递归中的重复计算。

package main

import "fmt"

// 动态规划求解斐波那契数列
func fibonacci(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]
}

func main() {
	fmt.Println(fibonacci(10)) // 输出: 55
}

2. 最长上升子序列（Longest Increasing Subsequence, LIS）

这个问题要求找到一个序列的最长上升子序列的长度。

package main

import "fmt"

// 动态规划求解最长上升子序列长度
func lengthOfLIS(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	dp := make([]int, len(nums))
	maxLen := 1
	for i := range dp {
		dp[i] = 1
		for j := 0; j < i; j++ {
			if nums[i] > nums[j] {
				dp[i] = max(dp[i], dp[j]+1)
			}
		}
		maxLen = max(maxLen, dp[i])
	}
	return maxLen
}

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

func main() {
	nums := []int{10, 9, 2, 5, 3, 7, 101, 18}
	fmt.Println(lengthOfLIS(nums)) // 输出: 4
}

3. 编辑距离（Edit Distance）

编辑距离问题要求计算将一个字符串转换成另一个字符串所需要的最少操作次数。

package main

import "fmt"

// 动态规划求解编辑距离
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], min(dp[i][j-1], dp[i-1][j])) + 1
			}
		}
	}

	return dp[m][n]
}

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

func main() {
	word1 := "horse"
	word2 := "ros"
	fmt.Println(minDistance(word1, word2)) // 输出: 3
}

这些例子展示了动态规划在解决不同类型问题时的应用。在实际编码中，你可能需要根据问题的具体情况调整状态定义和状态转移方程。动态规划是一个强大的工具，但它也需要一定的练习才能熟练掌握。

hot-100

动态规划

1. 斐波那契数列

2. 最长上升子序列（Longest Increasing Subsequence, LIS）

3. 编辑距离（Edit Distance）