动态规划入门：从斐波那契到背包问题

动态规划是算法面试的重点。本文介绍动态规划的基本概念。

什么是动态规划？

将问题分解为子问题，保存子问题的解，避免重复计算。

斐波那契数列

// 递归（慢）
int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

// 动态规划（快）
int fib(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

0-1 背包问题

int knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[][] dp = new int[n + 1][capacity + 1];
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= capacity; j++) {
            if (weights[i - 1] <= j) {
                dp[i][j] = Math.max(
                    dp[i - 1][j],
                    dp[i - 1][j - weights[i - 1]] + values[i - 1]
                );
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    
    return dp[n][capacity];
}

解题步骤

1. 定义状态：dp[i] 表示什么
2. 状态转移方程：dp[i] 和 dp[i-1] 的关系
3. 初始条件：dp[0] 的值
4. 计算顺序：从前往后还是从后往前

总结

动态规划的核心是状态定义和状态转移方程。多练习，掌握常见模型，可以解决大部分 DP 问题。