在記憶一步

Question

迴文分區DP複雜的問題，我有以下問題：

給定一個字符串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())); 
    } 
}