Leetcode 1000. Minimum Cost to Merge Stones

[Woodyiiiiiii]

这是一系列区间DP类型专题。

区间DP有别于一般的线性DP，记录的对象是区间。所以一般用二维数组记录(Java)，数组范围不会很大。

参考资料：

• 【图解】区间 DP：状态设计与优化（Python/Java/C++/Go）
• 区间 DP：最长回文子序列 最优三角剖分【基础算法精讲 22】

一般有两种写法，记忆化搜索和递推迭代搜索。要确立好递归入口、递归边界条件和递推公式。

相似题目：

• 1039. Minimum Score Triangulation of Polygon
• 375. Guess Number Higher or Lower II
• 516. Longest Palindromic Subsequence
• 1000. Minimum Cost to Merge Stones
• 132. Palindrome Partitioning II

---

看完No.1039和No.375后，来看看No.516。

这道题同样可以用区间DP。迭代写法的区别是因为i是从i+1推导出来的，所以要倒序迭代。递归写法和迭代写法分别如下：

class Solution {
    int n;
    int[][] memo;

    public int longestPalindromeSubseq(String s) {
        n = s.length();
        memo = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(memo[i], -1);
        }
        return dfs(s, 0, n - 1);
    }

    private int dfs(String s, int i, int j) {
        if (i == j) {
            return 1;
        } else if (i > j) {
            return 0;
        }
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        if (s.charAt(i) == s.charAt(j)) {
            memo[i][j] = 2 + dfs(s, i + 1, j - 1);
        } else {
            memo[i][j] = Math.max(dfs(s, i + 1, j), dfs(s, i, j - 1));
        }
        return memo[i][j];
    }
}

class Solution {
    int n;
    int[][] memo;

    public int longestPalindromeSubseq(String s) {
        n = s.length();
        memo = new int[n][n];
        for (int i = n - 1; i >= 0; --i) {
            memo[i][i] = 1;
            for (int j = i + 1; j < n; ++j) {
                if (s.charAt(i) == s.charAt(j)) {
                    memo[i][j] = memo[i + 1][j - 1] + 2;
                } else {
                    memo[i][j] = Math.max(memo[i + 1][j], memo[i][j - 1]);
                }
            }
        }
        return memo[0][n - 1];
    }
}

这样看来，区间DP应用于连续区间，从空间状态上来看是一个倒三角形，上大下小。

当然，这道题还有另一种思路。将字符串s反转，然后求反转后的字符串与s的最长公共子序列。

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n + 1][n + 1];
        String rev = new StringBuilder(s).reverse().toString();
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (s.charAt(i - 1) == rev.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j - 1], Math.max(dp[i][j - 1], dp[i - 1][j]));
                }
            }
        }
        return dp[n][n];
    }
}

---

No.1000。

这题难点在于多了变量k。这里就要引用三维数组。

class Solution {
    int[] stones;
    int[] sums;
    int n, k;
    int[][][] dp;

    public int mergeStones(int[] stones, int k) {
        this.stones = stones;
        this.n = stones.length;
        this.k = k;
        if ((n - 1) % (k - 1) != 0) {
            return -1;
        }
        sums = new int[n + 1];
        for (int i = 0; i < n; i++) {
            sums[i + 1] = sums[i] + stones[i];
        }
        dp = new int[n][n][k + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                Arrays.fill(dp[i][j], -1);
            }
        }
        return dfs(0, n - 1, 1);
    }

    private int dfs(int i, int j, int p) {
        if (dp[i][j][p] != -1) {
            return dp[i][j][p];
        }
        if (p == 1) {
            return dp[i][j][p] = i == j ? 0 : dfs(i, j, k) + sums[j + 1] - sums[i];
        }
        int res = Integer.MAX_VALUE;
        for (int m = i; m < j; m += k - 1) {
            res = Math.min(res, dfs(i, m, 1) + dfs(m + 1, j, p - 1));
        }
        return dp[i][j][p] = res;
    }
}