概述
动态规划提供了一种求最优问题的手段，本质上是通过合理的安排计算顺序而避免重复计算。解决动态规划问题主要在于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];
}
};
