动态规划从简单到复杂

今天咱们来聊聊动态规划，这个东西在算法题里太常见了，我平时刷题的时候，总觉得它像个老朋友，从简单入手就能逐步推到高级优化。咱们不废话，直接拿个经典题练手：斐波那契数列。问题是，给定一个数n，求斐波那契序列的第n项（从0开始，f(0)=0, f(1)=1, f(2)=1...）。

我第一次遇这个题的时候，就想用递归直奔主题。思路简单：f(n) = f(n-1) + f(n-2)，边界是n=0或1直接返回。但递归有问题，重复计算太多，比如f(5)会算好几次f(3)，时间复杂度指数级，n大点就爆了。代码这么写：

public int fib(int n) {
    if (n == 0) return 0;
    if (n == 1 || n == 2) return 1;
    return fib(n - 1) + fib(n - 2);
}

这玩意儿简单，但效率低。我想，得优化。加个记忆化搜索，用个数组存已经算过的值，避免重复。数组memo[n]存f(n)，初始化-1表示没算过。递归时先查memo，有就直接用，没就算完存进去。这样时间复杂度降到O(n)，空间也O(n)。思路是从顶向下，边算边记。

public int fibMemo(int n) {
    int[] memo = new int[n + 1];
    Arrays.fill(memo, -1);
    return process(n, memo);
}

private int process(int n, int[] memo) {
    if (n == 0) return 0;
    if (n == 1 || n == 2) return 1;
    if (memo[n] != -1) return memo[n];
    memo[n] = process(n - 1, memo) + process(n - 2, memo);
    return memo[n];
}

记忆化好使，但我觉得还能从底向上推。动态规划的本质就是填表，定义dp[i]为第i项的值。dp[0]=0, dp[1]=1，然后for循环从2到n，dp[i] = dp[i-1] + dp[i-2]。这样空间O(n)，时间O(n)，而且没有递归栈的风险。思路是先把小问题解了，再推大问题。

public int fibDP(int n) {
    if (n == 0) return 0;
    if (n == 1 || n == 2) return 1;
    int[] dp = new int[n + 1];
    dp[1] = 1;
    dp[2] = 1;
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

这已经很好了，但空间还能压。我发现，每次只用前两个值，不需要整个数组。用两个变量pre和cur，迭代更新。pre初始1（f1），cur初始1（f2），然后从3到n，temp = pre + cur, pre=cur, cur=temp。空间O(1)，时间还是O(n)。这优化让我觉得动态规划的思维就是不断压缩状态。

public int fibOptimize(int n) {
    if (n == 0) return 0;
    if (n == 1 || n == 2) return 1;
    int pre = 1;
    int cur = 1;
    for (int i = 3; i <= n; i++) {
        int temp = pre + cur;
        pre = cur;
        cur = temp;
    }
    return cur;
}

斐波那契是入门，练练手。现在升级，聊聊0-1背包问题。给定容量W的背包，N个物品，每个有重量w[i]和价值v[i]，每个物品只能选一次，求最大价值。

我先想暴力递归：对每个物品，选或不选。process(index, rest)表示从index开始，剩余容量rest的最大价值。base case：index==N，返回0。递归：不选=process(index+1, rest)，选（如果w[index]<=rest）=v[index] + process(index+1, rest - w[index])，取max。但重复子问题多，时间指数级。

public int knapsackRecursive(int[] w, int[] v, int N, int W) {
    return process(w, v, 0, W, N);
}

private int process(int[] w, int[] v, int index, int rest, int N) {
    if (index == N) return 0;
    int p1 = process(w, v, index + 1, rest, N);
    int p2 = 0;
    if (w[index] <= rest) {
        p2 = v[index] + process(w, v, index + 1, rest - w[index], N);
    }
    return Math.max(p1, p2);
}

加记忆化：用二维数组dp[index][rest]存结果。-1表示没算过。思路一样，但查表避免重复。

public int knapsackMemo(int[] w, int[] v, int N, int W) {
    int[][] dp = new int[N + 1][W + 1];
    for (int[] row : dp) Arrays.fill(row, -1);
    return processMemo(w, v, 0, W, dp);
}

private int processMemo(int[] w, int[] v, int index, int rest, int[][] dp) {
    if (dp[index][rest] != -1) return dp[index][rest];
    if (index == w.length) {
        dp[index][rest] = 0;
        return 0;
    }
    int p1 = processMemo(w, v, index + 1, rest, dp);
    int p2 = 0;
    if (w[index] <= rest) {
        p2 = v[index] + processMemo(w, v, index + 1, rest - w[index], dp);
    }
    dp[index][rest] = Math.max(p1, p2);
    return dp[index][rest];
}

转严格DP表：dp[i][j]表示前i个物品，容量j的最大价值。i从N到0，j从0到W。dp[N][j]=0所有j。for i=N-1 downto 0, for j=0 to W: dp[i][j] = max(dp[i+1][j], j>=w[i] ? v[i]+dp[i+1][j-w[i]] : 0)。时间O(NW)，空间O(NW)。

public int knapsackDP(int[] w, int[] v, int N, int W) {
    int[][] dp = new int[N + 1][W + 1];
    for (int i = N - 1; i >= 0; i--) {
        for (int j = 0; j <= W; j++) {
            int p1 = dp[i + 1][j];
            int p2 = 0;
            if (j >= w[i]) {
                p2 = v[i] + dp[i + 1][j - w[i]];
            }
            dp[i][j] = Math.max(p1, p2);
        }
    }
    return dp[0][W];
}

优化空间：因为每行只依赖下一行，用一维数组dp[j]，从后往前填（j=W downto 0），dp[j] = max(dp[j], j>=w[i] ? v[i]+dp[j-w[i]] : 0)。空间O(W)。

public int knapsackOptimize(int[] w, int[] v, int N, int W) {
    int[] dp = new int[W + 1];
    for (int i = 0; i < N; i++) {  // 注意这里从0到N-1
        for (int j = W; j >= w[i]; j--) {  // 从后往前
            dp[j] = Math.max(dp[j], v[i] + dp[j - w[i]]);
        }
    }
    return dp[W];
}

动态规划的思维就是这样，从暴力到记忆化，到表，到优化。每个题多练几种解法，思路就活了。下次咱们聊LIS啥的，继续提升。