动态规划

概述

动态规划提供了一种求最优问题的手段，本质上是通过合理的安排计算顺序而避免重复计算。解决动态规划问题主要在于2个方面：

1. 寻找递归公式
2. 确定计算顺序

题目

Longest Palindromic Subsequence

典型动态规划算法，递推公式如下：

d[i][j]表示在(i, j) 里面最长的回文子串，存在如下递推公式：
dp[i][j] = 
    dp[i+1][j-1] + 2,              if s[i] == s[j]
    max(dp[i][j-1], dp[i+1][j]),   if s[i] != s[j]

只要按照确定的顺序遍历，即可得到答案。可以辅助画一个二维数组图来获得遍历顺序, 可以发现按照如下顺序遍历可满足减少重复计算需求：

遍历顺序示意图

可以观察到i, j的距离是从0~size-1变化，具体代码如下：

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int dp[s.length()][s.length()];
        memset(dp, 0, sizeof(int)* s.length() * s.length());
        int i, j;
        for (int dis = 0; dis < s.length(); ++dis) {
            for (i = 0; (j = i + dis) < s.length(); ++i) {
                if (dis == 0) {
                    dp[i][j] = 1;
                }
                else if (s[i] == s[j]) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                }
                else {
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
                }
            }
        }
        return dp[0][s.length()-1];
    }
};