💰 动态规划实战：打家劫舍、完全平方数与零钱兑换（LeetCode 198 / 279 / 322）

本篇博客一次性带你掌握三道 LeetCode 中经典的动态规划（DP）题目：

• 🏠 198. 打家劫舍（House Robber）
• 🟩 279. 完全平方数（Perfect Squares）
• 💸 322. 零钱兑换（Coin Change）

它们覆盖了动态规划中的线性状态转移、完全背包问题，以及最小子结构决策问题。

🏠 一、198. 打家劫舍

📌 题目描述

一排房子，每个房子里有一定金额的钱，不能偷相邻的两个房子。求最多能偷多少钱？

💡 解题思路

这是一个典型的线性动态规划问题。

设 dp[i] 表示前 i 个房子最多能偷的钱：

• 偷第 i 个房子 → 前 i - 2 个房子最大值 + nums[i]
• 不偷第 i 个房子 → 前 i - 1 个房子最大值

状态转移方程为：

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

✅ Go 实现（空间优化版）

func rob(nums []int) int {
   
    if len(nums) == 0 {
   
        return 0
    }
    if len(nums) == 1 {
   
        return nums[0]
    }
    prev, curr := 0, 0
    for _, num := range nums {
   
        prev, curr = curr, max(curr, prev+num)
    }
    return curr
}

func max(a, b int) int {
   
    if a > b {
   
        return a
    }
    return b
}

🟩 二、279. 完全平方数

📌 题目描述

给你一个整数 n，将其表示为若干个完全平方数的和，求这些数的最少数量。

💡 解题思路

这是一个典型的完全背包问题。

• 状态定义：dp[i] 表示组成 i 所需的最少平方数数量；
• 状态转移：尝试每一个 j*j <= i 的平方数：

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

✅ Go 实现

func numSquares(n int) int {
   
    dp := make([]int, n+1)
    for i := 1; i <= n; i++ {
   
        dp[i] = i // 最坏情况：1+1+1+...+1
        for j := 1; j*j <= i; j++ {
   
            dp[i] = min(dp[i], dp[i - j*j] + 1)
        }
    }
    return dp[n]
}

func min(a, b int) int {
   
    if a < b {
   
        return a
    }
    return b
}

💸 三、322. 零钱兑换

📌 题目描述

给定不同面额的硬币 coins 和总金额 amount，求最少的硬币数量使得总金额为 amount。如果没有一种组合能组成，返回 -1。

💡 解题思路

也是典型的完全背包问题，区别在于：

• 目标是最小硬币数
• 状态定义：dp[i] 表示组成金额 i 所需最少的硬币数
• 初始化：dp[0] = 0，其余为 inf（表示不可达）

状态转移方程：

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

✅ Go 实现

func coinChange(coins []int, amount int) int {
   
    dp := make([]int, amount+1)
    for i := 1; i <= amount; i++ {
   
        dp[i] = amount + 1
    }

    for _, coin := range coins {
   
        for i := coin; i <= amount; i++ {
   
            dp[i] = min(dp[i], dp[i - coin] + 1)
        }
    }

    if dp[amount] > amount {
   
        return -1
    }
    return dp[amount]
}

🔚 总结对比

📘 写在最后

这三道题虽然看起来背景完全不同，但本质上都属于一维动态规划问题，熟悉它们可以极大提升你解决复杂 DP 问题的能力。

建议继续练习类似题目：

• 1. 打家劫舍 II（环形房屋）
• 1. 三角形最小路径和
• 1. 最长递增子序列