遍历方向

满足以下条件即可

1、遍历的过程中，所需的状态必须是已经计算出来的。

2、遍历的终点必须是存储结果的那个位置。

举例

最长回文子串

转移方程: dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]

1. 先上->下 后左->右

public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        String ans = "";
        for(int l = 0;l<n;l++){
            for (int i = 0; i + l < n; ++i) {
                int j = i+l;
                if(l==0){
                    dp[i][j] = true;
                }else if(l==1){
                    dp[i][j] = (s.charAt(i)==s.charAt(j));
                }else{
                    dp[i][j] = (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]);
                }
                if(dp[i][j]&&l+1>ans.length()){
                    ans = s.substring(i,i+l+1);
                }
            }
        }
        return ans;
    }

//等效
for (int i = 0; i < len; i++) {
	dp[i][i] = true;
}
for (int j = 1; j < len; j++) {
    for (int i = 0; i < j; i++) {
        if (charArray[i] != charArray[j]) {
            dp[i][j] = false;
        } else {
            if (j - i < 3) {
                dp[i][j] = true;
            } else {
                dp[i][j] = dp[i + 1][j - 1];
            }
        }
        if (dp[i][j] && j - i + 1 > maxLen) {
            maxLen = j - i + 1;
            begin = i;
        }
    }
}

2. 先左->右 后上->下

动态规划遍历方向

原文：https://www.cnblogs.com/jobyterry/p/14612269.html