回文分区 DP 复杂性问题在记忆步骤中

Question

我有以下问题：

给定一个字符串 s，对 s 进行分区，使得 分区是一个回文。

返回 s 的回文分区所需的最小切口。

我得到了正确的解决方案，但我缺少优化步骤，尤其是 DP 中所需的记忆步骤。

public int minCut(String a)   {
    if (isValidPal(a)) {
        return 0;
    }
    return minCut(a, 0, 0);
}
int min = Integer.MAX_VALUE;
private int minCut(String a, int cut, int index) {
    // too many cuts already
    if(cut >= min) return min;
    // out of index
    if (index >= a.length()) {
        // what is left is a pal
        if (isValidPal(a)) {
            min = Math.min(min, cut);
            return cut;
        }
        return Integer.MAX_VALUE;
    }
    int newCut = Integer.MAX_VALUE;
    if (isValidPal(a.substring(0, index + 1))) {
        // then cut
        newCut = minCut(a.substring(index + 1), cut + 1, 0);
    }
    // continue either way
    newCut = Math.min(minCut(a, cut, index + 1), newCut);
    return newCut;
}
HashMap<String, Boolean> memo  = new HashMap<>();
private boolean isValidPal(String s) {
    if(memo.containsKey(s)) {
        return memo.get(s);
    }
    boolean result = true;
    for (int i = 0; i < s.length() / 2; i++) {
        if (s.charAt(i) != s.charAt(s.length() - i - 1)) {
            result =  false;
            break;
        }
    }
    memo.put(s, result);
    return result;
}

Answer 1

尝试添加一个备忘录来存储你的计算结果，假设你的算法是正确的，这应该做优化

Map<String, Integer> dp = new HashMap<>();
private int minCut(String a, int cut, int index) {
// too many cuts already
if(cut >= min) return min;
String key = cut + " " + index;
//test if the memo contains the answer if yes return it
if(dp.containsKey(key)) return dp.get(key);
// out of index
if (index >= a.length()) {
    // what is left is a pal
    if (isValidPal(a)) {
        min = Math.min(min, cut);
        return cut;
    }
    return Integer.MAX_VALUE;
}
int newCut = Integer.MAX_VALUE;
if (isValidPal(a.substring(0, index + 1))) {
    // then cut
    newCut = minCut(a.substring(index + 1), cut + 1, 0);
}
// continue either way
newCut = Math.min(minCut(a, cut, index + 1), newCut);
//put the computed answer in the memo table
dp.put(key, newCut);
return newCut;

}

Answer 2

很

抱歉，但我的回答是基于您的代码是正确的事实，这是一个带有记忆的最小回文分区的工作示例

import java.util.*;
class Main {
  static HashMap<String, Integer> memo = new HashMap<>();
  static String s;
  static int f(int i, int j){
    if(i == j) return 0;
    if(isPalindrom(s.substring(i, j))) return 0;
    String key = i + " " + j;
    if(memo.containsKey(key)) return memo.get(key);
    int ans = 999999;
    for(int k = i; k < j; k++){
      ans = Math.min(ans, f(i, k) + f(k + 1, j) + 1);
    }
    memo.put(key, ans);
    return ans;
  }
  static boolean isPalindrom(String s){
    return s.equals(new StringBuilder(s).reverse().toString());
  }
  public static void main(String[] args) {
    s = "aaka";
    System.out.println(f(0, s.length()));
  }
}