摘要：本文介绍了动态规划法的基本概念，通过详细解析动态规划法的特征，给出判断问题是否使用动态规划法结题的思路。
本文分享自华为云社区《五大基础算法--动态规划法》，作者： 大金（内蒙的）。

  一、基本概念

动态规划法，和分治法极其相似。区别就是，在求解子问题时，会保存该子问题的解，后面的子问题求解时，可以直接拿来计算。

  专业的说法是：
对于一个规模为n的问题，将其分解为k个规模较小的子问题（阶段），按顺序求解子问题，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，通过决策求得局部最优解，依次解决各子问题。最后可以通过简单的判断，得到原问题的解。

  说法有些晦涩难懂，我给大家解释下：
阶段：求解第n个子问题称为第n个阶段。动态规划是按照顺序去求解子问题的，这里子问题的求解顺序很重要。
状态：在求解第n个阶段时，已求解n-1个阶段的解，称为状态。
决策：在求解第n个阶段时，根据状态和计算规则，可以得到第n个阶段时解。

  二、基本特征
动态规划法所能解决的问题一般具有以下几个特征：

  1) 大问题可分解性
该问题可以分解为若干个规模较小的问题，即该问题具有最优子结构性质。

  2) 子问题易解决性
该问题的规模缩小到一定的程度就可以容易地解决

  3) 解可合并性
利用该问题分解出的子问题的解可以合并为该问题的解；

  4) 子问题重叠性
当计算出某个子问题的解时，后续多个问题都需要计算该子问题的解，所以在计算某个子问题的解，将其保存，就节省了分治法重复计算的时间。

  三、一些误解
  1.状态转移方程
很多博客都说什么状态转移方程，感觉说的很高大上，一般解题上来就是状态转移方程是xxxx，代码是xxxx，翻译下是什么意思呢？
在求解第n个子问题的时候，通过已求解n-1个阶段的解和计算规则，可以得到第n个阶段时解。
即是最新的状态=目前的状态+决策。

  2.初始化
很多题目解题的时候都说初始化，这并不是动态规划法的步骤。应该正确的去理解这些操作。动态规划在划分子问题求解顺序时，基本是先求解易求解最小的子问题，在由这些已经求解的阶段+计算规则，就能直接求得第n阶段的解。所以初始化的含义是，求得初始阶段的解。

  3.边界条件
一般题目会说边界是啥，可以理解为怎么判断所有的子问题已经求解结束了。正常人也不会写while（true）吧，你总得让程序结束，判断你已经解决好这个问题了。

  四、动态规划法的基本步骤
  step1 分解：
将一个问题分解为多个子问题，需要注意子问题解决的顺序，应该先求解易求解的子问题，且后续的阶段可以通过前面的阶段+决策得到。

  step2 状态转移：
通过得到的规律，写出状态转移方程。
第n阶段=当前状态+决策（前n个阶段解和计算规则）

  step3 写代码：
将最先算的阶段计算出来，中间阶段通过状态转移方程计算状态，直到所有阶段计算结束。

  step4 得到解：
所有阶段计算结束，可以通过简单的统计，例如Max，Min等遍历阶段的值，得到最后的解。

  五、经典问题
好记性不如烂笔头，有一些适用动态规划法的问题，可以帮我们不断强化的解题思想。在解决问题时，希望大家可以注意判断题目的解决思路，看是否符合动态规划法的四个特征，这样不断强化，才能将算法掌握。

  最长回文子串
下面附上我的题解：
https://leetcode-cn.com/problems/longest-palindromic-substring/solution/dong-tai-gui-hua-fa-qiu-jie-kan-bu-dong-octkt/
  1. //动态规划法两个基本要素：最优子结构性质和子问题重叠性质。
  2. //很多答案写了初始化和边界条件，个人认为你要分清楚他的目的是什么。
  3. //很多初始化和边界条件，是因为状态转移方程，是需要初始化的子问题的解，从而避免重复计算，说白了还是子问题重叠和最优子结构问题。
  4. //我们应该注重某一个问题的重叠子问题分解和状态最优的决策分析。
  5. //解题思路:
  6. //计算某个字符串时, 如果它首尾字符相等，则它是不是回文，取决于去掉头尾之后的字符串是否为回文串。
  7. //                  如果它首尾字符不相等，则它一定不是回文
  8. //leetcode submit region begin(Prohibit modification and deletion)
  9. class Solution {
  10.     public String longestPalindrome(String s) {
  11.         int len = s.length();
  12.         // 特判
  13.         if (len < 2){
  14.             return s;
  15.         }
  17.         int maxLen = 1;
  18.         int begin  = 0;
  20.         // 1. 状态定义
  21.         // dp[i][j] 表示s[i...j] 是否是回文串，现在表示全部为0，不是回文串
  22.         boolean[][] dp = new boolean[len][len];
  23.         char[] chars = s.toCharArray();
  24.         // 2. 子问题计算顺序：先计算短字符串，在计算长字符串，同时根据已求得的短字符串或者计算规则，可以得到长字符串的解。
  26.             // 注意：s表示计算的元素顺序。
  27.         //     0   1   2  3  4
  28.         // 0   xx s1  s2 s4 s7
  29.         // 1      xx  s3 s5 s8
  30.         // 2          xx s6 s9
  31.         // 3             xx s10
  32.         // 4                xx
  33.         // 为什么这么写呢，因为你要保证保证计算某个元素时，通过状态转移方程能得到左上角元素的dp[][]。
  34.         // 填表规则：先一列一列的填写，再一行一行的填，保证计算某个元素时，它左上方的单元格已经被计算出了结果
  35.         // 填表规则：当然你也可以由左往右一行一行写，这样也能保证计算某个元素时，它左上方的单元格已经被计算出了结果
  36.         for (int j = 1;j < len;j++){
  37.             for (int i = 0; i < j; i++) {
  38.                 // 头尾字符不相等，不是回文串
  39.                 if (chars[i] != chars[j]){
  40.                     dp[i][j] = false;
  41.                 }else {
  42.                     // 相等的情况下
  43.                     // 因为考虑头尾去掉以后没有字符剩余，或者剩下一个字符的时候，肯定是回文串
  44.                     if (j - i -1 <= 1){
  45.                         dp[i][j] = true;
  46.                     }else {
  47.                         // 头尾相等，中间有大于1个元素，这个时候，我们无法直接判断他是不是回文，但是我们可以通过状态转移方程去判断
  49.                         // 其实这个就是在计算s8这个元素时，我们无法判断dp[1][4]在1和4位元素相等时候，整个字符串是否是回文。
  50.                         // 所以要通过s4去判断，s4是回文，s8就是。s4不是，那s8就不是。
  51.                         dp[i][j] = dp[i + 1][j - 1];
  52.                     }
  53.                 }
  55.                 // 只要dp[i][j] == true 成立，表示s[i...j] 是否是回文串
  56.                 // 此时更新记录回文长度和起始位置
  57.                 if (dp[i][j] && (j - i + 1 > maxLen)){
  58.                     maxLen = j - i + 1;
  59.                     begin = i;
  60.                 }
  61.             }
  62.         }
  64.         // 3. 初始化  
  65.         // 很多答案写了这个，这一步，我们细想，其实完全没有必要。
  66.         // 因为主对角线，值是可以直接判断出来的。
  67.         // 而且在求解过程中，我们的状态转移方程不会用到这个值。因为只有主对角线会用到这几个值。
  68.         // 而且单个元素的子问题解，我们并不需要。
  69.         // 所以，即使我这步初始化放到计算之后，甚至是直接去掉，也完全不影响结果。大家可以自己试一下
  70.         // for (int i = 0; i < len; i++) {
  71.         //     dp[i][i] = true;
  72.         // }
  73.         // 4. 返回值
  74.         return s.substring(begin,begin + maxLen);
  75.     }
  76. }