动态规划是近年来笔试和面试做常考的题型了。但是很难有一个模板去套所有的题型。我们结合力扣的题型来说说动态规划。
首先动态规划的问题一般都是最值问题，最短距离，最小序列，最长序列之类的。我们人看待问题可以左到统筹全局然后找出最值。但是电脑不行，电脑解决最值问题的唯一方法就是穷举。找出所有的解决方案，然后从中比较得出最优解。
也就是说绝大部分的问题都可以使用穷举得到答案。但是这里存在两个问题：一是很多问题不是那么容易穷举，需要我们找出一个合理的关系（转移方程），不然很难做到穷举出所有的值。而是存在重叠问题，会存在大量的重复计算，这使得算法的时间复杂度和空间复杂度都特别大。
第二个问题常规的做法是使用备忘录，最常用的就是加dp数组记录之前的值，但是这里一个难点就是dp[i]的定义是什么，这个很重要，影响到第一个问题的解决，第一个问题是在明确了dp[i]含义之后，如何写出转移方程。写转移方程最常用的就是数学归纳法，假设我们已经求出了dp[i-1],那么我们如何求出dp[i]呢。写转移方程的时候又需要明确dp[0]、dp[i]和dp[i-1]逻辑关系。
这里总结一下：我们的方法是我们的方法是穷举，但是要解决重叠问题，所以要找到最优子结构。我们要做的工作就是：
1.明确dp[i]的含义
2.写出bese case
3.写出转移方程
下面我介绍几个典型的例题：（这里的例题结构我借鉴了labuladong大佬写的动态规划文章，大佬写的特别好）
最长递增子序列
300. 最长上升子序列
注意「子序列」和「子串」这两个名词的区别，子串一定是连续的，而子序列不一定是连续的。
首先明确dp[i]定义，表示以nums[i]为结尾的最长递增子序列的长度。
这里要说明一下，我最开始的想法是表示0-i的最长递增子序列长度。也就是不一定要以nums[i]为结尾。这样的话就存在一个问题，如何得出dp[i]呢，因为nums[i]大于nums[i-1]也不一定得出dp[i]=dp[i-1]+1；所以这样设定的话，很难找到适合的转移方程。
有上面的定义可知base case是将dp[i]初始化为1，因为每一个自身都可以作为一个子序列。
下面就要写转移方程了。举个例子，我们现在已经求出了第6个数组元素的dp了，现在要求第7个。那么问题来了，我们要求的一定是最长的，前面6个元素可能不止一个比它小，就要求要比较一下，保存最大，所以只需要遍历之前的元素，维护最大值即可。
代码如下
class Solution { public int lengthOfLIS(int[] nums) { int[] dp=new int[nums.length]; for(int i=0;i<nums.length;i++){ dp[i]=1; } for(int i=0;i<nums.length;i++){ for(int j=0;j<i;j++){ if(nums[i]>nums[j]){ dp[i]=Math.max(dp[i],dp[j]+1); } } } //需要多做这一步 int res=0; for(int i=0;i<dp.length;i++){ res=Math.max(res,dp[i]); } return res; } }最大子数组
53. 最大子序和
首先dp[i]表示已nums[i]为结尾的最大子数组和，处于同样的原因，如果dp[i]表示0-i的最大子数组和，那么此时的最大子数组和不一定和nums[i-1]有关系，很难找到一个合适的转移方程。
base case就很好写了，直接为0就行
转移方程，对nums[i]来说，要么就加入最大子数组和，要么就自己作为一个子数组。
转移方程为
dp[i]=Math.max(nums[i],nums[i]+dp[i-1])代码如下：
public int maxSubArray(int[] nums){ if(nums.length==0) return 0; int[] dp=new int[nums.length]; dp[0]=0; for(int i=1;i<nums.length;i++){ dp[i]=Math.max(nums[i],nums[i]+dp[i-1]); } int res=Integer.MIN_VALUE; for(int i-0;i<nums.length;i++){ res=Math.max(res,dp[i]); } return res; }这里可以看到，其实只用到了dp[i]和dp[i-1]，因此可以降低空间复杂度
public int maxSubArray(int[] nums){ if(nums.length==0) return 0; int dp_0=nums[0],dp_1=0; int res=dp_0; for(int i=1;i<nums.length;i++){ dp_1=Math.max(nums[i],nums[i]+dp_0); dp_0=dp_1; res=Math.max(res,dp_1); } return res; }还可以在优化一下
class Solution { public int maxSubArray(int[] nums) { int sum=0; int max1=nums[0]; for(int i=0;i<nums.length;i++) { if(sum>0) sum+=nums[i]; else sum=nums[i]; max1=Math.max(sum,max1); } return max1; } }5. 最长回文子串
这个题目处理可以使用中心扩散法也可以使用动态规划，而且动态规划具有普遍性。
首先确定dp【i】【j】表示s[i]到是s[j]是否是回文子串，是为ture，否为false。
base case则是所有的dp【i】【i】为true
转移方程为：
当s[i]!=s[j]时，dp【i】【j】=false
当s[i]==s[j]时，dp【i】【j】=dp【i+1】【j-1】
这里存在一个问题，如果i=j-1的时候，此时是不构成闭区间的，如果i=j-2的时候，恰好是dp【j-1】【j-1】
因此当s[i]==s[j]时，如果j-i<3,dp【i】【j】=true,否则dp【i】【j】=dp【i+1】【j-1】
代码如下
class Solution { public String longestPalindrome(String s) { int maxlen=1; //记录最长回文子串长度 int index=0; //记录最长回文子串的起始位置 char[] ch=s.toCharArray(); int len=s.length(); if(len==0) return ""; if(len==1) return String.valueOf(ch[0]); boolean[][] dp=new boolean[len][len]; for(int i=0;i<len;i++){ dp[i][i]=true; //base case } for(int j=1;j<len;j++){ for(int i=0;i<j;i++){ if(ch[i]!=ch[j]){ dp[i][j]=false; }else{ if(j-i<3){ dp[i][j]=true; }else{ dp[i][j]=dp[i+1][j-1]; } } if(dp[i][j] && j-i+1>maxlen){ maxlen=j-i+1; index=i; } } } return s.substring(index,index+maxlen); } }
