经历过很多算法题，其中最常见的解题方法便是动态规划。
相关概念
动态规划（dynamic programming,即DP)，是一种常见的求解最优解的方案，他通过将复杂的问题拆分为单阶段的小问题求解，核心思想是递推，通过简单基础的解一步步接近最优解。
寻求最优解
对于一个算法问题，总有一个相对令人满意的解，但却不一定是我们想要的最优解，譬如在解决动态规划中最经典的背包问题时，有些人首先想到简单省心的贪心算法，取价值最高或是性价比最高的物品组合，这种方案得到的很有可能是最优解，但贪心的算法并不适用于动态规划领域，若是物品中恰好有能将背包塞得很满的组合，而采用贪心策略却浪费了很多背包空间。其实贪心策略本身更多也是一种“相对最优”的解决方案，而很少是真正的最优，这一点请务必斟酌。
阶数
通常解一个dp的算法题解是通过一个已知答案的解按表达式推导到最终我们想要的结果，依据题目的复杂程度会有不同的阶数，譬如最简单的爬楼梯解题所求是一个数组，那么它是一个一阶问题，但是背包问题所求是一个二维的表格（涉及到重量、价值两个维度的求解），所以它是二阶问题。问题的阶数将直接影响到推导问题的难度和其执行的时间复杂度。
无后效性
动态规划的题目都有这样的一种特性：给出了发展阶段中的某一个状态，状态会受到且只会受到该状态前的多个状态影响，而之后的状态不会影响到此刻。譬如：在爬楼梯问题中，当我们已经求出到n节楼梯的问题答案f(n)，后面无论怎样爬楼梯，都不会对f(n)造成影响。无后效性是一个问题能够采用动态规划思路解题的首要前提。
状态转移方程
这是动态规划领域中最核心的概念，可以说一个问题能推导出状态转移方程，一个问题就已经求出大半了，这个方程表达了我们要求的状态与之前状态的关系，可以通过它将由我们已知解的状态推导至待求的未知解，例如在爬楼梯问题中，我们假设f(n)为当台阶为n阶时的解，那么有：
以上便是题目的状态转移方程，通过方程可以很容易的利用递归写出解题的方法。
动态规划的适用性和解题过程
适用性和局限性
不得不提的是，并不是所有类型的问题只要能被拆分成最优子结构就可以利用动态规划解题，通常我们选择动态规划是因为题目具有如下的特征：
所求最优解，所求的策略必须可以拆分为子结构；
必须满足无后效性，每一个状态都只能受到历史状态的影响；
在满足前两点的基础上，将牺牲时间复杂的的搜索算法改为牺牲空间复杂度的动态规划算法，使用动态规划的解题是应为它做到了尽可能高的节省了解题效率
解题思路
求解动态规划问题的思路一般都是一成不变的：
分析题目，判断问题的状态，首先确定题目可以拆分最优子结构并且适合使用动态规划解决；
求出需要的已知解，构造状态转移方程
通过状态转移方程编写算法
我们可以采用两种基本的方式接近最优解，一个是自底向上由已知解逐渐填充数组直至待求解，一个是自顶向下利用递归最终到达已知解。比较常见的解法是从0推导数组到n，当我们面对多维度的DP也是如此，从(0,0)逐渐推导。
例题们
此处例题均来源于LeetCode，我会标出题号以便于在力扣官网查看。
简单难度：爬楼梯
leetcode70：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？(n>0)
这个题目可以说是动态规划的经典入门题，上面已经举了例子，我们假设f(n)是该题的解，显而易见，f(1)=1,f(2)=2。
接下来推导，当我们要走到第n阶时，我们仅有两种选择：从n-1走1步或是从n-2走两步，这两种解集独立没有交集，则状态转移方程为：
求解过程就很简单了：
public int climbStairs(int n) {
//从1到n的f(n)结果集
int[] dp = new int[n];
dp[0] = 1;
dp[1] = 2;
for(int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n-1];
}
中等难度1：最小路径和
leetcode64：给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:[[1,3,1], [1,5,1], [4,2,1]] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。
显然，此题是一个二维DP，我们可以设定到达网格的(m,n)（假设我们的起点是0,0）位置最小数字和为f(m,n)，并且假设网格中的数字值为v(m,n)，则f(0,0)=v(0,0)。
而垂直或者水平的一排解也很容易求得，比如在上面的例题中，有：
f(m,n)=[[1,4,5], [2,?,?], [6,?,?]]
即f(m,0)=f(m-1,0)+v(m,0)，f(0,n)=f(0,n-1)+v(n,0)，这样我们就准备好了此题求解的基本数据集。
然后我们聚集到m和n均大于0的情况下，想要到达某一点，只有两种方式：从上面的点向下走或是从左面的点向右走，我们要做的就是选择两种路径中数字和最小的，状态转移方程为：
public int minPathSum(int[][] grid) {
if(grid == null) return 0;
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(i ==0 && j == 0){
dp[i][j] = grid[i][j];
}else if(i == 0){
//只能从上边
dp[i][j] = dp[i][j-1]+grid[i][j];
} else if(j == 0){
//只能从左边
dp[i][j] = dp[i-1][j]+grid[i][j];
}else{
dp[i][j] = Math.min(dp[i][j-1], dp[i-1][j])+grid[i][j];
}
}
}
return dp[m-1][n-1];
}
中等难度2：打家劫舍
leetcode213：你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 :
输入: [2,3,2] 输出: 3 解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
此题相对较为复杂，我们可能很容易联想到可以令f(n)为前n个房子的最优解，但是由于房屋围成了一圈，其状态转移方程没那么好推导，我们可以先假定房子不是连续的，那么假设房子存放金额为v(n)，n个房子最优解为f(n)，则f(0)=v(0)，f(1)=max(0,1)，f(n)=max(f(n-1),f(n-2)+v(n))，是个不难推导的一维DP，但是很显然这种情景没有顾及可能同时偷窃了第一间和最后一间这种其实不符合题意的解法。所以我们可以计算两条Dp：假设屋子是0-n，我们可以假设他会偷第一间房屋即求解0到n-1的dp解集，同时在假设他没有偷第一间而可能偷到了最后一间，即求解1到n的dp解集，两者的解集最大值就是我们要求的值，我们求解两条线f1(n)，f2(n)，分别代表其在0到n-1和1到n的解集，则状态转移方程为（假设从0到n一共有n+1间房子）：
所以最终解法为：
class Solution{
public int rob(int[] nums) {
int n=nums.length;
if(n==1){
return nums[0];
}
return Math.max(robrob(nums,0,n-2),robrob(nums,1,n-1));
}
public int robrob(int[] nums,int start,int end){
int n=nums.length;
int [] dp=new int[n+2];
for(int i=end;i>=start;i--){
dp[i]=Math.max(dp[i+1],dp[i+2]+nums[i]);
}
return dp[start];
}
}
2020-03-11鱼鱼