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

所以你看，我从 M[0][0] 朝另一个方向前进，但我没有迭代地做。但我想应该没问题。只需要确认。

谢谢

4

2 回答 2

1

方向无关紧要。更重要的是你从更一般（复杂）的问题转向更简单的问题。你所做的是动态规划。

于 2014-06-07T13:23:38.173 回答
1

对于动态编程，遵循自下而上或自上而下的范式并不重要。动态规划的基本论点（正如您正确提到的）被称为贝尔曼的最优性原理，如下所示：

最优性原则：最优策略具有这样的性质：无论初始状态和初始决策是什么，其余决策都必须构成关于第一个决策产生的状态的最优策略。

资源：维基百科（http://en.wikipedia.org/wiki/Bellman_equation#Bellman.27s_Principle_of_Optimality）

从递归调用树中删除其中一些最佳子解决方案的一种很好的方法是使用缓存（就像在您的代码中一样）。

于 2014-06-07T13:31:44.373 回答