基本思想
将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
适用条件
①最优化原理：一个最优化策略的子策略总是最优的
②无后向性：即以前的决策无法直接影响未来的决策，未来的决策只取决于现在的状态
③子问题的重叠：关键在于解决程序的冗余；动态规划实际上是以空间换时间的手段
使用步骤
①总结规律
②列出状态转移方程式
③使用以往的结果进行最后的最优解
例题
题目：
最长回文子串（要求使用动态规划完成）：
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = “babad” 输出：“bab” 解释：“aba” 同样是符合题意的答案。 示例 2：
输入：s = “cbbd” 输出：“bb” 示例 3：
输入：s = “a” 输出：“a” 示例 4：
输入：s = “ac” 输出：“a”
提示：
1 <= s.length <= 1000 s 仅由数字和英文字母（大写和/或小写）组成
分析：
首先：什么是回文串？
对于字符串s来说，只有s[i，j]是回文串且s[i+1，j-1]必须相等，才可以把一个字符串s称为回文串。
状态转移方程：P{i,j} = P{i+1,j-1}&&{Si==Sj}
解题方案：
public class Solution {
public String longestPalindrome(String s) {
int n = s.length();
//如果字符串长度小于2，则返回他自己
if (n < 2) {
return s;
}
//定义此时的最大长度为1
int maxN = 1;
int begin = 0;
//定义boolean类型的二维数组
boolean[][] a = new boolean[n][n];
//初始化boolean类型二维数组
//boolean类型的二维数组默认为false，遍历该数组，并把对角线的值改为true
for (int i = 0; i < n; i++) {
a[i][i] = true;
}
//把字符串s中的字符存入char类型的数组中
char[] Array = s.toCharArray();
for (int j = 1; j < n; j++) {
for (int i = 0; i < j; i++) {
//如果左边界i和右边界j不相等，则直接为false
if (Array[i] != Array[j]) {
a[i][j] = false;
} else {
//如果右边界j减去左边界i的长度小于等于2.则改为true
if (j - i < 3) {
a[i][j] = true;
} else {//如果长度大于2，则需要判断i和j里面的字符是否相等
a[i][j] = a[i + 1][j - 1];
}
}
//如果a[i][j] == true;就表示子串s[i...j]是回文串，此时记录回文长度和起始位置
if (a[i][j] && j - i + 1 > maxN) {
maxN = j - i + 1;
begin = i;
}
}
}
//通过substring方法截取字符串s的回文字符
return s.substring(begin, begin + maxN);
}
public static void main(String[] args) {
String s = "asdfllfdsa";
Solution solution = new Solution();
System.out.println(solution.longestPalindrome(s));
}
}
结果：
总结：
动态规划是一种舍弃空间来换取时间的方法；他最不便捷的地方在于动态规划没有一个固定的“套路”，在解题过程中，需要解题人根据实际情况和问题的性质进行解决；并且他拥有“维数障碍”，当变量的维数急剧增大时，受于计算机的限制，无法使用动态规划进行问题的解决。