1278. Palindrome Partitioning III

 一刷 06/2022

Version #1 DP

主要的难点在于初始化的状态和递推公式

首先对于n=1的情况所有的substring i 的dp答案都是min moves

然后就是在递推 dp[i] = min{dp[j] + minMove(j, i - 1)}的时候，这里的j是不能到0的，因为如果j到了0，就不可能分割成n个部分，这里的解就是invalid

正确的做法是j > = n-1，也就是说 substring [0, j) 有长度为j个chars，如果一个char是一个partition，就有j个partition，j一定要大于等于n-1才能保证一定能分成n-1个partition

Time O(KN^2)

Space O(N^2)

Runtime: 7 ms, faster than 62.57% of Java online submissions for Palindrome Partitioning III.

Memory Usage: 42.4 MB, less than 34.76% of Java online submissions for Palindrome Partitioning III.

class Solution {

    public int palindromePartition(String s, int k) {

        // dp[i][n] - min moves to split substring [0, i) into n parts

        int[] dp = new int[s.length() + 1];

        int[][] move = new int[s.length() + 1][s.length() + 1];

        for (int end = 1; end < s.length(); end++) {

            for (int start = end - 1; start >= 0; start--) {

                // when start == end, move[start][end] = 0

                move[start][end] = move[start + 1][end - 1] + (s.charAt(start) == s.charAt(end) ? 0 : 1);

            }

        }

        for (int n = 1; n <= k; n++) {

            int[] currDP = new int[s.length() + 1];

            for (int i = 1; i <= s.length(); i++) {

                if (n == 1) {

                    currDP[i] = move[0][i - 1];

                } else {

                    currDP[i] = Integer.MAX_VALUE;

                    // check how many moves can change substring[j, i) into palindrome

                    for (int j = i - 1; j >= n - 1; j--) {

                        currDP[i] = Math.min(currDP[i], dp[j] + move[j][i - 1]);

                    }

                }

            }

            dp = currDP;

        }

        return dp[s.length()];

    }

}