简单来说，就是之前的问题和现在的问题有关联性，需要记住之前做过的事或者记住之前计算得到的结果来帮助解决当前的问题。动态规划常常适用于有重叠子问题和最优子结构性质的问题
以空间换时间
最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。
无后效性。即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。
子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。
问题拆解，找到问题之间的具体联系
状态定义
递推方程推导
实现
假如你正在爬楼梯，每次可以爬1或2个台阶，一共n个台阶，那么有多少种不同的方法可以爬到楼顶？
思考
到达n层的方法就等于到达n-1层的方法加上到达n-2层的方法，到达n-1层以及n-2层的方法数可以依次往下拆解，直到到达1层有1种方法，到达2层有2种方法。
参考代码
1 public int climbStairs(int n) { 2 if (n == 1) { 3 return 1; 4 } 5 int[] dp = new int[n + 1]; // 多开一位，考虑起始位置 6 dp[0] = 0; dp[1] = 1; dp[2] = 2; 7 for (int i = 3; i <= n; ++i) { 8 dp[i] = dp[i - 1] + dp[i - 2]; 9 } 10 return dp[n]; 11 }
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例：输入[-1, 3, 4, -5, 4, 1] 输出 7
思考
记录到i为止前面的最大子序和，不用考虑子数组的位置，只考虑最大和。取i-1的最大子序和与当前节点的最大值（若取后者，说明新的一轮加和开始）,即若前面的最大子序和小于0则开始新的加和。
代码
1 public int maxSubArray(int[] nums) { 2 if (nums == null || nums.length == 0) { 3 return 0; 4 } 5 int n = nums.length; 6 int[] dp = new int[n]; 7 dp[0] = nums[0]; 8 int result = dp[0]; 9 for (int i = 1; i < n; ++i) { 10 dp[i] = Math.max(dp[i - 1], 0) + nums[i]; 11 result = Math.max(result, dp[i]); 12 } 13 return result; 14 }
有数组penny，penny中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim(小于等于1000)代表要找的钱数，求换钱有多少种方法。给定数组penny及它的大小(小于等于50)，同时给定一个整数aim，请返回有多少种方法可以凑成aim。
思考
状态的记录：记录下分别使用0-n种货币达到数值0-aim的方法数
初始条件，可知dp[i][0]=1，对于第一行dp[0][j]，表示只用penny[0]这种货币进行拼凑，那么只有该货币的整数倍的钱数才能拼凑成功。所以dp[0][j]=1（j是penny[0]的倍数），否则dp[0][j]=0。
对于任意的一个值dp[i][j]表示使用arr[0~i]的元素来拼凑出目标值为j的方案数目，总结规律可以发现：dp[i][j]=dp[i-1][j]+dp[i-1][j-penny[i]]+dp[i-1][j-penny[i]*2]+...即penny[i]选0,1,2，...个时的情况，这个式子可以进一步简化，如图所示 dp[i-1][j-penny[i]]+dp[i-1][j-penny[i]*2]+...的计算结果就是dp[i][j-penny[i]]的计算结果，于是dp[i][j]= dp[i-1][j]+ dp[i][j-penny[i]]
参考代码
1 public int in(int[] penny, int n, int aim) { 2 if(n == 0 || penny == null || aim < 0){ 3 return 0; 4 } 5 int [][] dp = new int[n][aim+1]; 6 for(int i = 0; i< n; i++) { 7 dp[i][0] = 1; 8 } 9 for(int i = 1; penny[0]*i <= aim; i++) { 10 dp[0][penny[0]*i] = 1; 11 } 12 for(int i = 1; i < n;i++) { 13 for(int j = 0;j <= aim;j++) { 14 if(j >= penny[i]) { 15 dp[i][j] = dp[i-1][j] + dp[i][j-penny[i]]; 16 }else { 17 dp[i][j] = dp[i-1][j]; 18 } 19 } 20 } 21 return dp[n-1][aim]; 22 }
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。 例如，给定三角形：
[ [2], [3,4], [6,5,7], [4,1,8,3] ]
自顶向下的最小路径和为11（2+3+5+1=11）
注意： 如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。
思考
和爬楼梯类似，这里有两种思考方式，一种是自顶向下，一种是自下往上。若是自顶往下，则在考虑下面的元素的时候， 起始元素的路径只会从[i - 1][j] 获得，每行当中的最后一个元素的路径只会从 [i - 1][j - 1] 获得，中间取两者的最小值，这样记录下到达当前节点的最小路径和，最后一行的最小值即最终最小值。若是自下往上，每个元素都会从[i+1][j]以及[i+1][j+1]处获得，这样子最后结果的[0][0]即为最终结果。
代码示例
// 自顶往下
1 public int triangle(List<List<Integer>> tri) { 2 int n = tri.size(); 3 int [][]dp = new int[n][n]; 4 dp[0][0] = tri.get(0).get(0); 5 for(int i = 1; i < n; i++) { 6 dp[i][0] = dp[i-1][0] + tri.get(i).get(0); 7 for(int j = 1; j < i; j++) { 8 dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j]) + tri.get(i).get(j); 9 System.out.println(dp[i][j]); 10 } 11 dp[i][i] = dp[i-1][i-1] + tri.get(i).get(i); 12 } 13 int result = dp[n-1][0]; 14 for(int d:dp[n-1]){ 15 result = Math.min(result, d); 16 } 17 return result; 18 }
// 自下往上
1 public int minimumTotal(List<List<Integer>> triangle) { 2 int n = triangle.size(); 3 int[][] dp = new int[n][n]; 4 List<Integer> lastRow = triangle.get(n - 1); 5 for (int i = 0; i < n; ++i) { 6 dp[n - 1][i] = lastRow.get(i); 7 } 8 for (int i = n - 2; i >= 0; --i) { 9 List<Integer> row = triangle.get(i); 10 for (int j = 0; j < i + 1; ++j) { 11 dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + row.get(j); 12 } 13 } 14 return dp[0][0]; 15 }
一个人在方格最左上角，每次只能往下或往右走，能有多少种方法到达某个点？
思考
由于只能往下或往右走，所以在某一点上[i][j]上，他只能从[i-1][j]或者[i][j-1]到达，因此到达[i][j]的方法等于到达[i-1][j]与[i][j-1]的方法之和。
参考代码
1 public int uniquePaths(int m, int n) { 2 int[][] dp = new int[m][n]; 3 for (int i = 0; i < m; ++i) { 4 dp[i][0] = 1; 5 } 6 for (int j = 0; j < n; ++j) { 7 dp[0][j] = 1; 8 } 9 for (int i = 1; i < m; ++i) { 10 for (int j = 1; j < n; ++j) { 11 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; 12 } 13 } 14 return dp[m - 1][n - 1]; 15 }
拓展
如果在方格种存在障碍物呢？
到达障碍物点的方法数设为0就ok了
子序列，说明这个公共序列不一定连续，比如sdjikop的一个序列为diop
思考
参考代码
1 public static int findLCS(String A, int n, String B, int m) { 2 int[][] dp = new int[n + 1][m + 1]; 3 for (int i = 0; i <= n; i++) { 4 for (int j = 0; j <= m; j++) { 5 dp[i][j] = 0; 6 } 7 } 8 for (int i = 1; i <= n; i++) { 9 for (int j = 1; j <= m; j++) { 10 if (A.charAt(i - 1) == B.charAt(j - 1)) { 11 dp[i][j] = dp[i - 1][j - 1] + 1; 12 } else { 13 dp[i][j] = dp[i - 1][j] > dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1]; 14 } 15 } 16 } 17 return dp[n][m]; 18 }
参考内容：
https://blog.csdn.net/u012813201/article/details/75270891
https://blog.csdn.net/qbyhqp/article/details/82050535
原文：https://www.cnblogs.com/vert/p/DP.html