Является ли следующий подход динамическим программированием

Question

Насколько я знаю, 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] в другом направлении, но я не делаю это итеративно. Но я думаю, это должно быть хорошо. Просто нужно подтвердить.

Спасибо

Answer 1

Направление не имеет значения. Что важнее, так это то, что вы переходите от более общих (сложных) проблем к более простым. То, что вы сделали, это динамическое программирование.

Answer 2

Для динамического программирования не имеет значения, если вы будете следовать восходящей или нисходящей -парадигме. Основной тезис (как вы правильно упомянули) динамического программирования известен как принцип оптимальности Беллмана, а именно:

Принцип оптимальности. Оптимальная политика обладает тем свойством, что какими бы ни были исходное состояние и первоначальное решение, остальные решения должны составлять оптимальную политику в отношении состояния, являющегося результатом первого решения.

Ресурс: Википедия ( http://en.wikipedia.org/wiki/Bellman_equation)

Отличным подходом к вырезанию некоторых из этих оптимальных подрешения из дерева рекурсивных вызовов является использование кэширования (как в вашем коде).