动态规划（Dynamic Programming，简称DP）是一种通过把原问题拆分为相对简单的子问题的方式来求解复杂问题的方法。动态规划常常适用于有 重叠子问题 和 最优子结构 性质的问题，其方法耗时一般要少于朴素的暴力解法。

解题思路

  1. 确定基本问题的解
  2. 确定状态。即为问题中变化的量
  3. 确定选择。也就是导致状态发生变化的行为
  4. 依据状态列出状态转移方程

确定该状态上可以执行的操作，然后该状态和前一个状态或前多个状态有什么关联，通常该状态下可执行的操作必定可以关联到我们之前的状态
解题的模板：

  1. # 初始化 base case
  2. dp[0][0][...] = base
  3. # 进行状态转移
  4. for 状态1 in 状态1的所有取值：
  5.     for 状态2 in 状态2的所有取值：
  6.         for ...
  7.             dp[状态1][状态2][...] = 求最值(选择1，选择2...)

解题方式

1.先写出递归的解法

递归解法通常会包含大量的重复计算，可以画出递归树

2.自顶向下的备忘录法

递归的思考方式还是自顶向下，其中存在的重复计算是可以用备忘录存储的，因此可以引入Map等结构来保存已经计算的结构，砍掉很多重复计算的分支

3.自底向上

这种通常需要通过循环，先计算初始的值，然后依据状态转移方程，不断累积计算最终结果

经典动态规划问题

动态规划的相关问题通常题目有个特征就是 最值问题
LeetCode 1143. 最长公共子序列

  1. class Solution {
  2.     public int longestCommonSubsequence(String text1, String text2) {
  3.         int m = text1.length();
  4.         int n = text2.length();
  5.         if (m * n == 0) {
  6.             return 0;
  7.         }
  8.         int[][] dp = new int[m+1][n+1];
  9.         dp[0][0] = 0;
  10.         for (int i=1; i<=m ; i++) {
  11.             for (int j=1; j<=n ; j++) {
  12.                 if (text1.charAt(i-1) == text2.charAt(j-1)) {
  13.                     dp[i][j] = dp[i-1][j-1] + 1;
  14.                 } else {
  15.                     dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
  16.                 }
  17.             }
  18.         }
  19.         return dp[m][n];
  20.     }
  21. }

LeetCode 198. 打家劫舍

  1. class Solution {
  2.     public int rob(int[] nums) {
  3.         if (nums.length == 0) return 0;
  4.         if (nums.length == 1) return nums[0];
  5.         int[] dp = new int[nums.length];
  6.         dp[0] = nums[0];
  7.         dp[1] = Math.max(nums[0], nums[1]);
  8.         if (nums.length == 2) {
  9.             return dp[1];
  10.         }
  11.         for (int i=2; i< nums.length; i++) {
  12.             dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
  13.         }
  14.         return dp[nums.length-1];
  15.     }
  16. }

LeetCode 70. 爬楼梯

  1. class Solution {
  2.     public int climbStairs(int n) {
  3.         if (n<=2) {
  4.             return n;
  5.         }
  6.         //这里实际可以定义一个维度为n的数组，但是这里省略了，只用了两个
  7.         int t1= 1;
  8.         int t2= 2;
  9.         int c = t2;
  10.         for (int i=3; i<=n ;i++) {
  11.             c = t1+t2;
  12.             t1= t2;
  13.             t2= c;
  14.         }
  15.         return c;
  16.     }
  17. }

LeetCode 5. 最长回文子串

  1. class Solution {
  2.     public String longestPalindrome(String s) {
  3.         if (s == null || s.length() == 0) {
  4.             return s;
  5.         }
  6.         int len = s.length();
  7.         int left = 0;
  8.         int maxLength = 1;
  9.         //dp[i][j]表示下标为i到j的字符串是否为回文串
  10.         boolean[][] dp = new boolean[len][len];
  11.         for (int i=0; i< len;i++) {
  12.             dp[i][i] = true;
  13.         }
  14.         for (int j=1; j<len;j++) {
  15.             for (int i=0; i<j; i++) {
  16.                 //如果端点不同，则一定不是
  17.                 if (s.charAt(i) != s.charAt(j)) {
  18.                     dp[i][j] = false;
  19.                 } else {
  20.                     //只有两个或一个元素，则为true
  21.                     if (j-i < 3) {
  22.                         dp[i][j] = true;
  23.                     } else {
  24.                         //比较里面的元素
  25.                         dp[i][j] = dp[i+1][j-1];
  26.                     }
  27.                 }
  28.                 if (dp[i][j] && (j-i+1) > maxLength) {
  29.                     maxLength = j-i+1;
  30.                     left = i;
  31.                 }
  32.             }
  33.         }
  34.         return s.substring(left, left + maxLength);
  35.     }
  36. }