一维动态规划

难度：⭐⭐⭐⭐ | 核心思想：将大问题分解为重叠子问题，用数组记录子问题的解，避免重复计算。DP 的本质是"带备忘录的递归"。

LC70. 爬楼梯

题目：每次可以爬 1 或 2 个台阶，到达第 n 阶有多少种方法。

思路：到达第 i 阶的方法数 = 到达第 i-1 阶的方法数 + 到达第 i-2 阶的方法数。斐波那契数列。

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        a, b = 1, 2
        for _ in range(3, n + 1):
            a, b = b, a + b
        return b

复杂度：时间 O(n)，空间 O(1)

关键点：最简单的 DP 入门题。状态转移：dp[i] = dp[i-1] + dp[i-2]。空间优化：只需前两个状态。

---

LC198. 打家劫舍

题目：不能偷相邻的两间房屋，求能偷到的最高金额。

思路：到第 i 间房屋时，两个选择：偷（加上 i-2 的最大金额）或不偷（取 i-1 的最大金额）。

class Solution:
    def rob(self, nums: list[int]) -> int:
        if not nums:
            return 0
        if len(nums) <= 2:
            return max(nums)
        a, b = nums[0], max(nums[0], nums[1])
        for i in range(2, len(nums)):
            a, b = b, max(b, a + nums[i])
        return b

复杂度：时间 O(n)，空间 O(1)

关键点：dp[i] = max(dp[i-1], dp[i-2] + nums[i])——"抢当前"vs"不抢当前"的二选一。

---

LC279. 完全平方数

题目：给定正整数 n，返回和为 n 的最少完全平方数的个数。

思路：dp[i] 表示和为 i 的最少完全平方数个数。对每个 i，尝试用所有可能的完全平方数 j² 来凑。

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        for i in range(1, n + 1):
            j = 1
            while j * j <= i:
                dp[i] = min(dp[i], dp[i - j * j] + 1)
                j += 1
        return dp[n]

复杂度：时间 O(n × sqrt(n))，空间 O(n)

关键点：这是一个"完全背包"问题的变体——完全平方数就是"物品"，目标值 n 就是"背包容量"。

---

LC322. 零钱兑换

题目：给定面额数组 coins 和总金额 amount，求最少硬币数。无法凑出返回 -1。

思路：与 LC279 几乎相同，dp[i] 表示凑出金额 i 的最少硬币数。

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        for i in range(1, amount + 1):
            for coin in coins:
                if coin <= i:
                    dp[i] = min(dp[i], dp[i - coin] + 1)
        return dp[amount] if dp[amount] != float('inf') else -1

复杂度：时间 O(amount × |coins|)，空间 O(amount)

关键点：完全背包模板。如果先遍历 coins 再遍历 amount，则是"组合"（每种面额只用一次）；当前写法（先 amount 后 coins）是"排列"。对于求最少数量，两者结果相同。

---

LC300. 最长递增子序列

题目：给定整数数组 nums，找到最长严格递增子序列的长度。

思路：维护一个 tails 数组，tails[i] 表示长度为 i+1 的递增子序列的最小末尾元素。对每个元素，二分查找其在 tails 中的位置并替换。

import bisect

class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        tails = []
        for num in nums:
            pos = bisect.bisect_left(tails, num)
            if pos == len(tails):
                tails.append(num)
            else:
                tails[pos] = num
        return len(tails)

复杂度：时间 O(n log n)，空间 O(n)

关键点：tails 数组始终保持递增。bisect_left 找到第一个 ≥ num 的位置替换，这样可以保证 tails 尽可能小，为后续元素留出更多空间。注意 tails 不一定是真实的最长子序列，但长度是正确的。

---

总结

题目	DP 类型	状态转移
LC70	线性 DP	dp[i] = dp[i-1] + dp[i-2]
LC198	线性 DP	dp[i] = max(dp[i-1], dp[i-2] + nums[i])
LC279	完全背包	dp[i] = min(dp[i - j²] + 1)
LC322	完全背包	dp[i] = min(dp[i - coin] + 1)
LC300	LIS（贪心+二分）	tails 二分替换

一维 DP 的解题步骤：

1. 定义 dp 数组的含义
2. 找到状态转移方程
3. 确定初始条件
4. 考虑空间优化（能否用滚动变量）