0
據我所知，DP要麼是從更大的問題開始，遞歸地下降，並且每次都要保存值以備將來使用，或者迭代執行並保持值自下而上。但是如果我自下而上但遞歸地上升呢？以下方法動態編程
說，例如以下問題，Longest Common Subsequence
這裏是我的解決方案
public class LongestCommonSubseq {
/**
* @param args
*/
public static List<Character> list = new ArrayList<Character>();
public static int[][] M = new int[7][7];
public static void main(String[] args) {
String s1 = "ABCDGH";
String s2 = "AEDFHR";
for(int i=0;i<=6;i++)
for(int j=0;j<=6;j++)
M[i][j] = -1;
int max = getMax(s1,s2,0,0);
System.out.println(max);
Collections.sort(list);
for(int i = 0;i < max;i++)
System.out.println(list.get(i));
}
public static int getMax(String s1, String s2,int i ,int j){
if(i >= s1.length() || j>= s2.length()){
M[i][j] = 0;
return M[i][j];
}
if(M[i][j] != -1)
return M[i][j];
if(s1.charAt(i) == s2.charAt(j)){
M[i][j] = 1 + getMax(s1,s2,i+1,j+1);
list.add(s1.charAt(i));
}
else
M[i][j] = max(getMax(s1,s2,i+1,j) , getMax(s1, s2, i, j+1));
return M[i][j];
}
public static int max(int a,int b){
return a > b ? a : b;
}
}
所以你看，我從要去[0] [0]在另一個方向，但我沒有做它迭代。 但我想應該沒問題。只需要確認。
謝謝