跳到主要内容

多维动态规划

多维 DP 通常用于解决矩阵路径、字符串编辑、两个物体的组合状态迁移及买卖股票等问题。状态定义通常为 dp[i][j]。

120. 三角形最小路径和 (Triangle)​

题目描述​

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是下标与上一层结点下标相同或者等于上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

解题思路​

自底向上递归。

  1. dp[i][j]dp[i][j] 表示从底到 (i,j)(i, j) 的最小路径。
  2. dp[i][j]=min(dp[i+1][j],dp[i+1][j+1])+triangle[i][j]dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j]。
  3. 空间优化：可以直接在底层数组上通过一维数组覆盖记录。

Java 代码实现​

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] dp = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
            }
        }
        return dp[0];
    }
}

64. 最小路径和 (Minimum Path Sum)​

题目描述​

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明： 每次只能向下或者向右移动一步。

解题思路​

原地覆盖式的 DP。

  1. dp[i][j]=min(dp[i−1][j],dp[i][j−1])+grid[i][j]dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。
  2. 处理边缘：第一行和第一列仅能从左或上单向累加。

Java 代码实现​

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) continue;
                if (i == 0) grid[i][j] += grid[i][j - 1];
                else if (j == 0) grid[i][j] += grid[i - 1][j];
                else grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        return grid[m - 1][n - 1];
    }
}

62. 不同路径 (Unique Paths)​

题目描述​

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

解题思路​

二维路径累加。

  1. dp[i][j]dp[i][j] 表示到达 (i,j)(i, j) 的不同路径数。
  2. 状态转移：dp[i][j]=dp[i−1][j]+dp[i][j−1]dp[i][j] = dp[i-1][j] + dp[i][j-1]（当前位置只能从上方或左方移过来）。
  3. 初始值：第一行和第一列的所有位置路径数均为 1。
  4. 优化：可以使用一维数组进行 O(n) 的空间优化。

Java 代码实现​

class Solution {
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] += dp[j - 1];
            }
        }
        return dp[n - 1];
    }
}

188. 买卖股票的最佳时机 IV (Best Time to Buy and Sell Stock IV)​

题目描述​

给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买入 k 次，卖出 k 次。

**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

解题思路​

多状态 DP 数组。

  1. 类似于买卖股票 III（k=2 情况），这里维护 2k2k 个状态。
  2. buy[j] 表示第 j 次买入后的最大收益，sell[j] 表示第 j 次卖出后的最大收益。
  3. 转移方程：
    • buy[j] = max(buy[j], sell[j-1] - prices[i])
    • sell[j] = max(sell[j], buy[j] + prices[i])

Java 代码实现​

class Solution {
    public int maxProfit(int k, int[] prices) {
        if (prices.length == 0 || k == 0) return 0;
        int[] buy = new int[k + 1];
        int[] sell = new int[k + 1];
        Arrays.fill(buy, -prices[0]);
        for (int p : prices) {
            for (int j = 1; j <= k; j++) {
                buy[j] = Math.max(buy[j], sell[j - 1] - p);
                sell[j] = Math.max(sell[j], buy[j] + p);
            }
        }
        return sell[k];
    }
}

97. 交错字符串 (Interleaving String)​

题目描述​

给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。

两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：

  • s = s1 + s2 + ... + sn
  • t = t1 + t2 + ... + tm
  • 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...

注意： a + b 意味着字符串 a 和 b 连接。

解题思路​

二维路径匹配 DP。

  1. dp[i][j]dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符是否能交错组成 s3 的前 i+j 个字符。
  2. 转移逻辑：
    • 如果 s1[i−1]==s3[i+j−1]s1[i-1] == s3[i+j-1]，取决于 dp[i−1][j]dp[i-1][j]。
    • 如果 s2[j−1]==s3[i+j−1]s2[j-1] == s3[i+j-1]，取决于 dp[i][j−1]dp[i][j-1]。
  3. 初始值：dp[0][0]=truedp[0][0] = true。

Java 代码实现​

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length();
        if (m + n != s3.length()) return false;
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                int p = i + j - 1;
                if (i > 0) dp[i][j] = dp[i][j] || (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(p));
                if (j > 0) dp[i][j] = dp[i][j] || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(p));
            }
        }
        return dp[m][n];
    }
}

5. 最长回文子串 (Longest Palindromic Substring)​

题目描述​

给你一个字符串 s，找到 s 中最长的 回文子串 。

解题思路​

区间 DP 或 中心扩散。

  1. dp[i][j]dp[i][j]：子串 s[i…j]s[i \dots j] 是否为回文。
  2. 如果 s[i]==s[j]s[i] == s[j] 且 dp[i+1][j−1]dp[i+1][j-1] 为 true，则 dp[i][j]=truedp[i][j] = true。
  3. 枚举长度 len∈[1,n]len \in [1, n]。

Java 代码实现​

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length(), start = 0, max = 1;
        boolean[][] dp = new boolean[n][n];
        for (int i = 0; i < n; i++) dp[i][i] = true;
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    if (len <= 3 || dp[i + 1][j - 1]) dp[i][j] = true;
                }
                if (dp[i][j] && len > max) { max = len; start = i; }
            }
        }
        return s.substring(start, start + max);
    }
}

72. 编辑距离 (Edit Distance)​

题目描述​

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行三种操作：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

解题思路​

二维状态转移：增加、删除、替换。

  1. dp[i][j]dp[i][j] 表示 word1[0…i]word1[0 \dots i] 变成 word2[0…j]word2[0 \dots j] 的最小步数。
  2. 如果当前字符相同：dp[i][j]=dp[i−1][j−1]dp[i][j] = dp[i-1][j-1]。
  3. 否则考虑三种情况取最小：
    • 替换：dp[i−1][j−1]+1dp[i-1][j-1] + 1
    • 删除：dp[i−1][j]+1dp[i-1][j] + 1
    • 插入：dp[i][j−1]+1dp[i][j-1] + 1

Java 代码实现​

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
                else dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
            }
        }
        return dp[m][n];
    }
}

123. 买卖股票的最佳时机 III (Best Time to Buy and Sell Stock III)​

题目描述​

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

解题思路​

四状态转移控制。

  1. b1: 第一次买入；s1: 第一次卖出。
  2. b2: 第二次买入；s2: 第二次卖出。 状态机：s2 = max(s2, b2 + price), b2 = max(b2, s1 - price) 等。

Java 代码实现​

class Solution {
    public int maxProfit(int[] prices) {
        int b1 = -prices[0], s1 = 0, b2 = -prices[0], s2 = 0;
        for (int p : prices) {
            b1 = Math.max(b1, -p);
            s1 = Math.max(s1, b1 + p);
            b2 = Math.max(b2, s1 - p);
            s2 = Math.max(s2, b2 + p);
        }
        return s2;
    }
}

221. 最大正方形 (Maximal Square)​

题目描述​

在一个由 '0' 和 '1' 组成的 m x n 矩阵中，找到只包含 '1' 的最大正方形，并返回其面积。

解题思路​

左、上、左上角关系。

  1. dp[i][j]dp[i][j]：以 (i,j)(i, j) 为右下角的最大正方形边长。
  2. dp[i][j]=min(dp[i−1][j],dp[i][j−1],dp[i−1][j−1])+1dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。
  3. 只有当 grid[i][j]==′1′grid[i][j] == '1' 时更新。
  4. 结果为 max(dp[i][j])2max(dp[i][j])^2。

Java 代码实现​

class Solution {
    public int maximalSquare(char[][] matrix) {
        int m = matrix.length, n = matrix[0].length, maxLen = 0;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (matrix[i - 1][j - 1] == '1') {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    maxLen = Math.max(maxLen, dp[i][j]);
                }
            }
        }
        return maxLen * maxLen;
    }
}