0

私の知る限り、DP は、より大きな問題から始めて再帰的に降りてきて、将来の使用のために毎回値を保存し続けるか、繰り返し実行して値をボトムアップで保存し続けるかのいずれかです。しかし、ボトムアップで再帰的に行っている場合はどうなりますか?

たとえば、次の質問を考えてみましょう。最長共通部分列

これが私の解決策です

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;
}
}

ご覧のとおり、M[0][0] から別の方向に進んでいますが、繰り返し実行していません。でもきっといいはず。確認する必要がありました。

ありがとう

4

2 に答える 2

1

動的計画法の場合、ボトムアップまたはトップダウンのパラダイムに従うかどうかは問題ではありません。動的計画法の基本的なテーゼ (あなたが正しく述べたように) は、ベルマンの最適性の原則として知られています。これは次のとおりです。

最適性の原則: 最適なポリシーには、最初の状態と最初の決定が何であれ、残りの決定は、最初の決定から生じる状態に関して最適なポリシーを構成する必要があるというプロパティがあります。

リソース: ウィキペディア ( http://en.wikipedia.org/wiki/Bellman_equation#Bellman.27s_Principle_of_Optimality )

これらの最適なサブソリューションの一部を再帰呼び出しツリーから切り離すための優れたアプローチは、(コードのように) キャッシュを使用することです。

于 2014-06-07T13:31:44.373 に答える