Is the following approach dynamic programming

Question

As far as I know, DP is either you start with bigger problem and recursively come down, and keep saving the value each time for future use or you do it iteratively and keep saving values bottom up. But what if I am doing it bottom up but recursively going up?

Say for example the following question, Longest Common Subsequence

Here's my solution

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

So you see,I am going from M[0][0] in the other direction but I am not doing it iteratively. But I guess it should be fine. Just needed to confirm.

Thanks

Answer 1

The direction does not matter. What is more important is that you go from more general(complex) problem to simpler ones. What you have done is dynamic programming.

Answer 2

For dynamic programming it doesn't matter if you follow the bottom-up or top-down-paradigm. The basic thesis (like you have correctly mentioned) of dynamic programming is known as Bellman's Principle of Optimality which is the following:

Principle of Optimality: An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision.

Resource: Wikipedia (http://en.wikipedia.org/wiki/Bellman_equation#Bellman.27s_Principle_of_Optimality)

An great approach to cut of some of these optimal sub-solutions from the recursive-call-tree is to use Caching (like in your code).