跳至主要內容

区间 DP

大约 6 分钟

区间 DP

题目难度
516. 最长回文子序列open in new window中等灵神 b 站
1216. 验证回文字符串 IIIopen in new window 困难
1312. 让字符串成为回文串的最少插入次数open in new window困难
1682. 最长回文子序列 IIopen in new window 中等
1039. 多边形三角剖分的最低得分open in new window中等灵神 b 站
题目难度
546. 移除盒子open in new window困难
664. 奇怪的打印机open in new window困难
1000. 合并石头的最低成本open in new window困难
1278. 分割回文串 IIIopen in new window困难
1547. 切棍子的最小成本open in new window困难

定义

令状态 f(i,j) 表示将下标位置 i 到 j 的所有元素合并能获得的价值的最大值。

状态转移方程：f(i,j) = max{f(i,k) + f(k+1,j) + cost} (i<=k<j)

for (int span = 2; span <= n; span++)
    for (int i = 0; i + span - 1 < n; i++) {
        int j = i + span - 1;
        // ...
    }

516. 最长回文子序列

public class Solution516 {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        if (n == 1) return 1;
        char[] cs = s.toCharArray();
        // f[i][j] 表示 [i,j] 区间最长回文子序列的长度
        int[][] f = new int[n][n];
        for (int span = 2; span <= n; span++) {
            for (int i = 0; i + span - 1 < n; i++) {
                f[i][i] = 1;
                int j = i + span - 1;
                if (cs[i] == cs[j]) {
                    f[i][j] = f[i + 1][j - 1] + 2;
                } else {
                    f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
                }
            }
        }
        return f[0][n - 1];
    }
}

$1216. 验证回文字符串 III

public class Solution1216 {
    public boolean isValidPalindrome(String s, int k) {
        int n = s.length();
        char[] cs = s.toCharArray();
        // 区间 DP
        // f[i][j] = k 表示 [i,j] 是 k 回文
        int[][] f = new int[n][n];
        for (int span = 2; span <= n; span++) {
            for (int i = 0; i + span - 1 < n; i++) {
                int j = i + span - 1;
                f[i][j] = Math.min(f[i + 1][j] + 1, f[i][j - 1] + 1);
                if (cs[i] == cs[j]) {
                    f[i][j] = Math.min(f[i][j], f[i + 1][j - 1]);
                }
            }
        }
        return f[0][n - 1] <= k;
    }
}

1312. 让字符串成为回文串的最少插入次数

public class Solution1312 {
    public int minInsertions(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();
        // f[i][j] 表示 [i,j] 区间最少添加字符的数量，使 [i,j] 变为回文串
        int[][] f = new int[n][n];
        for (int span = 2; span <= n; span++) {
            for (int i = 0; i + span - 1 < n; i++) {
                int j = i + span - 1;
                f[i][j] = Math.min(f[i + 1][j], f[i][j - 1]) + 1;
                if (cs[i] == cs[j]) {
                    f[i][j] = Math.min(f[i][j], f[i + 1][j - 1]);
                }
            }
        }
        return f[0][n - 1];
    }
}

$1682. 最长回文子序列 II

public class Solution1682 {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();
        // 区间 DP
        // f[i][j] 表示 [i,j] 区间最长"好的回文子序列"的长度；g[i][j] 表示 [i,j] 两边最近的回文字符
        int[][] f = new int[n][n];
        char[][] g = new char[n][n];
        for (int span = 2; span <= n; span++) {
            for (int i = 0; i + span - 1 < n; i++) {
                int j = i + span - 1;
                if (cs[i] == cs[j] && (f[i + 1][j - 1] == 0 || g[i + 1][j - 1] != cs[i])) {
                    f[i][j] = f[i + 1][j - 1] + 2;
                    g[i][j] = cs[i];
                } else {
                    if (f[i + 1][j] > f[i][j - 1]) {
                        f[i][j] = f[i + 1][j];
                        g[i][j] = g[i + 1][j];
                    } else {
                        f[i][j] = f[i][j - 1];
                        g[i][j] = g[i][j - 1];
                    }
                }
            }
        }
        return f[0][n - 1];
    }
}

1039. 多边形三角剖分的最低得分

public class Solution1039 {
    public int minScoreTriangulation(int[] values) {
        int n = values.length;

        // 区间 DP
        int[][] f = new int[n][n];
        // f[i] 从 f[k] 转移过来，所以 i 要倒序枚举
        for (int i = n - 3; i >= 0; i--) {
            // f[i][j] 从 f[i][k] 转移过来，所以 j 要正序枚举
            for (int j = i + 2; j < n; j++) {
                int min = Integer.MAX_VALUE;
                for (int k = i + 1; k < j; k++) {
                    min = Math.min(min, f[i][k] + f[k][j] + values[i] * values[j] * values[k]);
                }
                f[i][j] = min;
            }
        }
        return f[0][n - 1];
    }
}

546. 移除盒子

import java.util.Arrays;

public class Solution546 {
    private int[] boxes;
    private int[][][] memo;

    public int removeBoxes(int[] boxes) {
        int len = boxes.length;
        this.boxes = boxes;

        memo = new int[len][len][len];
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                Arrays.fill(memo[i][j], -1);
            }
        }
        return f(0, len - 1, 0);
    }

    // f(l,r,k) 表示移除区间 [l,r] 的元素 加上该区间右边等于 ar 的 k 个元素组成的这个序列的最大积分
    private int f(int l, int r, int k) {
        if (l > r) {
            return 0;
        }
        if (memo[l][r][k] != -1) {
            return memo[l][r][k];
        }

        int r1 = r;
        int k1 = k;
        while (r1 > l && boxes[r1] == boxes[r1 - 1]) {
            r1--;
            k1++;
        }
        int max = f(l, r1 - 1, 0) + (k1 + 1) * (k1 + 1);
        for (int i = l; i < r1; i++) {
            if (boxes[i] == boxes[r1]) {
                max = Math.max(max, f(l, i, k1 + 1) + f(i + 1, r1 - 1, 0));
            }
        }
        memo[l][r][k] = max;
        return max;
    }
}

664. 奇怪的打印机

public class Solution664 {
    public int strangePrinter(String s) {
        int n = s.length();

        // f[i][j] 表示打印完成区间 [i,j] 的最少操作数
        int[][] f = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            f[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    f[i][j] = f[i][j - 1];
                } else {
                    int min = Integer.MAX_VALUE;
                    for (int k = i; k < j; k++) {
                        min = Math.min(min, f[i][k] + f[k + 1][j]);
                    }
                    f[i][j] = min;
                }
            }
        }
        return f[0][n - 1];
    }
}

1000. 合并石头的最低成本

public class Solution1000 {
    public int mergeStones(int[] stones, int k) {
        int n = stones.length;
        if ((n - 1) % (k - 1) != 0) {
            return -1;
        }

        // dp[i][j] 为尽可能多的合并区间 [i,j] 所需的成本，不一定能合并成一堆，但合并完成后剩下的堆数一定小于 k
        int[][] dp = new int[n + 1][n + 1];
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] + stones[i - 1];
        }
        // 枚举区间长度
        for (int len = k; len <= n; len++) {
            // 枚举区间起点
            for (int i = 1; i + len - 1 <= n; i++) {
                int j = i + len - 1;
                dp[i][j] = Integer.MAX_VALUE;
                // 枚举分界点
                for (int p = i; p < j; p += k - 1) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][p] + dp[p + 1][j]);
                }
                if ((j - i) % (k - 1) == 0) {
                    dp[i][j] += sum[j] - sum[i - 1];
                }
            }
        }
        return dp[1][n];
    }
}

1278. 分割回文串 III

import java.util.Arrays;

public class Solution1278 {
    public int palindromePartition(String s, int k) {
        int n = s.length();

        // 预处理
        int[][] cost = new int[n][n];
        for (int span = 2; span <= n; ++span) {
            for (int i = 0; i <= n - span; ++i) {
                int j = i + span - 1;
                cost[i][j] = cost[i + 1][j - 1] + (s.charAt(i) == s.charAt(j) ? 0 : 1);
            }
        }

        // f[i][j] 表示对于字符串 s 的前 i 个字符，将它分割成 j 个非空且不相交的回文串，最少需要修改的字符数
        int[][] f = new int[n + 1][k + 1];
        for (int i = 0; i < n + 1; i++) {
            Arrays.fill(f[i], Integer.MAX_VALUE);
        }
        f[0][0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= Math.min(k, i); ++j) {
                if (j == 1) {
                    f[i][j] = cost[0][i - 1];
                } else {
                    for (int i0 = j - 1; i0 < i; ++i0) {
                        f[i][j] = Math.min(f[i][j], f[i0][j - 1] + cost[i0][i - 1]);
                    }
                }
            }
        }
        return f[n][k];
    }
}

1547. 切棍子的最小成本

import java.util.Arrays;

public class Solution1547 {
    public int minCost(int n, int[] cuts) {
        int m = cuts.length;
        Arrays.sort(cuts);

        int[] cuts1 = new int[m + 2];
        for (int i = 1; i <= m; i++) {
            cuts1[i] = cuts[i - 1];
        }
        cuts1[m + 1] = n;

        // f[i][j] 表示 [i,j] 切棍子的 最小总成本
        int[][] f = new int[m + 2][m + 2];
        for (int i = m; i >= 1; i--) {
            for (int j = i; j <= m; j++) {
                f[i][j] = (i == j) ? 0 : Integer.MAX_VALUE;
                for (int k = i; k <= j; k++) {
                    f[i][j] = Math.min(f[i][j], f[i][k - 1] + f[k + 1][j]);
                }
                f[i][j] += cuts1[j + 1] - cuts1[i - 1];
            }
        }
        return f[1][m];
    }
}

（全文完）

Copyright © 2018-2023 gdut-yy