一维动态规划

动态规划 (DP) 的核心在于状态定义、状态转移方程和初始值。一维 DP 通常通过上一步的状态 dp[i-1] 或 dp[i-2] 计算当前状态。

70. 爬楼梯 (Climbing Stairs)

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

解题思路

斐波那契数列模型。

1. 第 n 阶楼梯只能由第 n-1 阶（爬一步）或第 n-2 阶（爬两步）到达。
2. $dp[i] = dp[i-1] + dp[i-2]$。
3. 初始值：$dp[1]=1, dp[2]=2$。

Java 代码实现

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        int a = 1, b = 2, c = 0;
        for (int i = 3; i <= n; i++) {
            c = a + b; a = b; b = c;
        }
        return b;
    }
}

---

198. 打家劫舍 (House Robber)

题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

解题思路

不偷当前 vs 偷当前。

1. $dp[i]$：抢劫到第 i 间房所能获得的最大财宝。
2. 如果偷第 i 间房：$dp[i] = dp[i-2] + nums[i]$。
3. 如果不偷第 i 间房：$dp[i] = dp[i-1]$。
4. 转移方程：$dp[i] = max(dp[i-1], dp[i-2] + nums[i])$。
5. 优化空间：仅需两个变量记录前两步。

Java 代码实现

class Solution {
    public int rob(int[] nums) {
        int pre = 0, curr = 0;
        for (int x : nums) {
            int tmp = curr;
            curr = Math.max(pre + x, curr);
            pre = tmp;
        }
        return curr;
    }
}

---

139. 单词拆分 (Word Break)

题目描述

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用 wordDict 中出现的一个或多个单词拼接成 s ，则返回 true 。

**注意：**不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

解题思路

布尔背包式 DP。

1. $dp[i]$：判断 $s[0:i]$ 是否可以拆分。
2. 遍历 $j < i$。如果 $dp[j]$ 为 true 且 $s[j:i]$ 在字典中，则 $dp[i] = true$。
3. 初始值：$dp[0] = true$。

Java 代码实现

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && set.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

---

322. 零钱兑换 (Coin Change)

题目描述

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

解题思路

全排列组合式 DP。

1. $dp[i]$：凑成金额 i 最少需要多少枚硬币。
2. 遍历每一个金额 $i$ 和每一个面额 $coin$。
3. 如果 $i - coin \ge 0$，则 $dp[i] = min(dp[i], dp[i-coin] + 1)$。
4. 初始值：$dp[0] = 0$，其余设为无穷大。

Java 代码实现

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int c : coins) {
                if (i - c >= 0) dp[i] = Math.min(dp[i], dp[i-c] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

---

300. 最长递增子序列 (Longest Increasing Subsequence)

题目描述

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

解题思路

单调栈思想或 DP。

1. $dp[i]$：以 $nums[i]$ 结尾的最长递增子序列长度。
2. 遍历 $j < i$。若 $nums[j] < nums[i]$，更新 $dp[i] = max(dp[i], dp[j] + 1)$。
3. 优化：$O(n \log n)$ 维护一个递增容器，贪心替换大值。

Java 代码实现

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length];
        int res = 0;
        for (int num : nums) {
            int i = 0, j = res;
            while (i < j) {
                int m = (i + j) / 2;
                if (tails[m] < num) i = m + 1;
                else j = m;
            }
            tails[i] = num;
            if (res == j) res++;
        }
        return res;
    }
}

(注：上述使用了 $O(n \log n)$ 的二分搜索配合 Tails 数组替换优化方案)。