golang 解法, 执行用时: 16 ms, 内存消耗: 7.3 MB, 提交时间: 2023-01-12 09:52:56

func minCut(s string) int {
    n := len(s)
    g := make([][]bool, n)
    for i := range g {
        g[i] = make([]bool, n)
        for j := range g[i] {
            g[i][j] = true
        }
    }
    for i := n - 1; i >= 0; i-- {
        for j := i + 1; j < n; j++ {
            g[i][j] = s[i] == s[j] && g[i+1][j-1]
        }
    }

    f := make([]int, n)
    for i := range f {
        if g[0][i] {
            continue
        }
        f[i] = math.MaxInt64
        for j := 0; j < i; j++ {
            if g[j+1][i] && f[j]+1 < f[i] {
                f[i] = f[j] + 1
            }
        }
    }
    return f[n-1]
}

python3 解法, 执行用时: 596 ms, 内存消耗: 42.7 MB, 提交时间: 2023-01-12 09:52:36

class Solution:
    def minCut(self, s: str) -> int:
        n=len(s)
        dp=[[False]*(n+1) for _ in range(n+1)]
        for i in range(n-1,-1,-1):
            for j in range(i,n):
                if s[i]==s[j]:
                    if j-i<=1:
                        dp[i][j]=True
                    else:
                        dp[i][j]=dp[i+1][j-1]
        f=[0]*n
        f[0]=1
        for i in range(1,n):
            f[i]=f[i-1]+1
            for j in range(i-1,-1,-1):
                if dp[j][i]:
                    f[i]=min(f[i],f[j-1]+1 if j>=1 else 1)
        return f[-1]-1 if dp[0][n-1]!=True else 0

java 解法, 执行用时: 54 ms, 内存消耗: 43.4 MB, 提交时间: 2023-01-12 09:52:01

class Solution {
    public int minCut(String s) {
        int n = s.length();
        boolean[][] g = new boolean[n][n];
        for (int i = 0; i < n; ++i) {
            Arrays.fill(g[i], true);
        }

        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                g[i][j] = s.charAt(i) == s.charAt(j) && g[i + 1][j - 1];
            }
        }

        int[] f = new int[n];
        Arrays.fill(f, Integer.MAX_VALUE);
        for (int i = 0; i < n; ++i) {
            if (g[0][i]) {
                f[i] = 0;
            } else {
                for (int j = 0; j < i; ++j) {
                    if (g[j + 1][i]) {
                        f[i] = Math.min(f[i], f[j] + 1);
                    }
                }
            }
        }

        return f[n - 1];
    }
}