01背包
01背包模板
func zeroOneKnapsack(weights []int, values []int, capacity int) int {n := len(weights)// dp[i][j] 表示：考虑前 i 个物品（索引从 0 到 i-1），容量为 j 时的最大价值dp := make([][]int, n+1)for i := range dp {dp[i] = make([]int, capacity+1)}// i 从 0 开始，表示我们现在要处理第 i 个物品（索引为 i）for i := 0; i < n; i++ {for j := 0; j <= capacity; j++ {// 不选第 i 个物品（索引为 i）dp[i+1][j] = dp[i][j]// 尝试选择第 i 个物品（索引为 i）if j >= weights[i] { // 直接使用 weights[i]，因为 i 就是索引// 选择的话，价值是：前 i 个物品在容量 j-weights[i] 下的最大价值 + 第 i 个物品的价值dp[i+1][j] = max(dp[i+1][j], dp[i][j-weights[i]] + values[i])}}}// dp[n][capacity] 仍然是最终答案：考虑所有 n 个物品（索引 0 到 n-1），容量为 capacity 时的最大价值return dp[n][capacity]
}
01背包变体
416. 分割等和子集
func canPartition(nums []int) bool {n := len(nums)sum := 0for _, num := range nums {sum += num}if sum % 2 == 1 {return false}target := sum / 2dp := make([][]bool, n + 1)for i := 0; i <= n; i ++ {dp[i] = make([]bool, target + 1)}dp[0][0] = truefor i := 0; i < n; i ++ {for j := 0; j <= target; j ++ {dp[i + 1][j] = dp[i][j]if j >= nums[i] {dp[i + 1][j] = dp[i + 1][j] || dp[i][j - nums[i]]}}}return dp[n][target]
}
完全背包
完全背包模板
func completeKnapsack(weights []int, values []int, capacity int) int {n := len(weights)// dp[i][j] 表示：考虑前 i 个物品（索引从 0 到 i-1），容量为 j 时的最大价值dp := make([][]int, n+1)for i := range dp {dp[i] = make([]int, capacity+1)}// i 从 0 开始，表示我们现在要处理第 i 个物品（索引为 i）for i := 0; i < n; i++ {for j := 0; j <= capacity; j++ {// 不选第 i 个物品（索引为 i）dp[i+1][j] = dp[i][j]// 尝试选择第 i 个物品（索引为 i）if j >= weights[i] {// 关键区别：完全背包用 dp[i][j-weights[i]]，而不是 dp[i-1][j-weights[i]]// 因为可以选择无限次，所以仍然考虑前 i 个物品（包括当前物品）dp[i+1][j] = max(dp[i+1][j], dp[i][j-weights[i]] + values[i])}}}return dp[n][capacity]
}
完全背包变体
322. 零钱兑换
func coinChange(coins []int, amount int) int {n := len(coins)dp := make([][]int, n + 1)for i := 0; i <= n; i++ {dp[i] = make([]int, amount + 1)for j := 0; j <= amount; j ++ {dp[i][j] = amount + 1}}dp[0][0] = 0for i := 0; i < n; i ++ {for j := 0; j <= amount; j ++ {dp[i + 1][j] = dp[i][j]if j >= coins[i] {dp[i + 1][j] = min(dp[i + 1][j], dp[i + 1][j - coins[i]] + 1)}}}res := dp[n][amount]if res > amount {return -1}return res
}
- 完全平方数
func numSquares(n int) int {// 生成所有平方数 <= nvar squares []inti := 1for i*i <= n {squares = append(squares, i*i)i++}// 完全背包函数return completeKnapsack(squares, n)
}func completeKnapsack(squares []int, capacity int) int {n := len(squares)// dp[i][j] 表示前 i 个平方数中，凑出总和为 j 的最小平方数个数dp := make([][]int, n+1)for i := range dp {dp[i] = make([]int, capacity+1)for j := range dp[i] {dp[i][j] = capacity + 1 // 初始化为一个大值}}dp[0][0] = 0 // 初始状态：0 个平方数凑出 0for i := 0; i < n; i++ {for j := 0; j <= capacity; j++ {// 不选当前平方数dp[i+1][j] = dp[i][j]// 选当前平方数（完全背包允许重复使用）if j >= squares[i] {dp[i+1][j] = min(dp[i+1][j], dp[i+1][j - squares[i]] + 1)}}}return dp[n][capacity]
}