动态规划实质就是先对问题进行解构，找到最小子问题。以leetcode120. 三角形最小路径和为例：
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。 相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。 例如，给定三角形： [ [2], [3,4], [6,5,7], [4,1,8,3] ] 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
现在想求这个有四层的三角形的最小路径，我们必须知道三层三角形的最小路径，根据转移条件从从第三层的每个结点到第四层都有两种路径，直接跳到正下方的结点或者正下方右边结点，也就是从(3,j)->(4,j)或(3,j)->(4,j+1)。
直接找到最小路径和是有困难的，要遍历所有可能的路径，但是假如已经知道到第三层每个结点的最小路径和，计算从第三层每个结点到第四层每个结点的最小路径是简单的。
到最左边结点的路径和：直接由到正上方结点的最小路径和加上自身得到。到最右边结点的路径和：直接由到上一层前一个结点的最小路径和加上自身得到。到中间结点的路径和：到上一层第i个结点和第i-1个结点的最小路径和加上自身得到。 这里要注意由于转移条件的限制，并不是每一层直接取最小值就能得到具有最小路径和的路径，能直接算的只是到每个结点的最小路径和，然后在进行比较。形式化描述为： dp[i][j]：为到第i层第j个节点的最小路径和 总结一下这个套路：
先将问题分解找到最基本的子问题，一般我们可以从前i个结果已知如何得到第i+1的结果这个角度入手。通过分析得到转移方程,想清楚dp数组的具体含义。想清楚如何初始化以及边界问题。 上代码： class Solution { public: int minimumTotal(vector<vector<int>>& triangle) { int n = triangle.size(); int m = triangle[n-1].size(); vector<vector<int>>dp(triangle); for(int i=1;i<n;i++){ for(int j = 0;j<=i;j++){ if(j==0){ dp[i][j] = dp[i-1][j]+dp[i][j]; }else if(j==i){ dp[i][j] = dp[i-1][j-1]+dp[i][j]; }else{ dp[i][j] = min(dp[i-1][j],dp[i-1][j-1])+dp[i][j]; } } } int ans = INT_MAX; for(int i=0;i<m;i++){ ans=min(dp[n-1][i],ans); } return ans; } };leetcode64. 最小路径和
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 说明：每次只能向下或者向右移动一步。 示例: 输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。
分析：
dp[i][j]：从左上角到（i,j）的最小路径和确定转移方程：每个dp(i,j)的值是根据左边和右边结点的值计算得到的，所以dp的计算方向应该是从左到右，从上到下。边界：dp[0][0]，初始状态：grid[0][0] class Solution { public: int minPathSum(vector<vector<int>>& grid) { int m = grid.size(),n = grid[0].size(); int dp[m][n];//从左上角到（m,n）的最小路径和 dp[0][0] = grid[0][0]; for(int i=1;i<m;i++) dp[i][0] = dp[i-1][0]+grid[i][0]; for(int i=1;i<n;i++) dp[0][i] = dp[0][i-1]+grid[0][i]; for(int i=1;i<m;i++){ for(int j =1;j<n;j++){ dp[i][j] = min(dp[i-1][j],dp[i][j-1])+grid[i][j]; } } return dp[m-1][n-1]; } };62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。 问总共有多少条不同的路径？ 例如，上图是一个7 x 3 的网格。有多少可能的路径？ 示例 1: 输入: m = 3, n = 2 输出: 3 解释: 从左上角开始，总共有 3 条路径可以到达右下角。
向右 -> 向右 -> 向下向右 -> 向下 -> 向右向下 -> 向右 -> 向右 示例 2: 输入: m = 7, n = 3 输出: 28 提示： 1 <= m, n <= 100 题目数据保证答案小于等于 2 * 10 ^ 9 分析： dp[i][j]：从左上角到（i,j）的不同路径条数确定转移方程：每个dp(i,j)的值是根据左边和右边结点的值计算得到的，所以dp的计算方向应该是从左到右，从上到下。边界：dp[0][0]，初始状态：0 class Solution { public: static const int maxn = 100; int dp[maxn][maxn]; int uniquePaths(int m, int n) { dp[0][0]; for(int i=0;i<n;i++) dp[i][0] = 1; for(int i=0;i<m;i++) dp[0][i]= 1; for(int i =1;i<n;i++){ for(int j =1;j<m;j++){ dp[i][j] = dp[i-1][j]+dp[i][j-1]; } } return dp[n-1][m-1]; } };63. 不同路径 II
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？ 网格中的障碍物和空位置分别用 1 和 0 来表示。 说明：m 和 n 的值均不超过 100。 示例 1: 输入: [ [0,0,0], [0,1,0], [0,0,0] ] 输出: 2 解释: 3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径：
向右 -> 向右 -> 向下 -> 向下向下 -> 向下 -> 向右 -> 向右分析：在上一题的基础上需要考虑当前单元的左边或上边单元有障碍物时，那这条路径就断了。
class Solution { public: static const int maxn= 100; int dp[maxn][maxn]; int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int m = obstacleGrid[0].size(),n = obstacleGrid.size(); if(obstacleGrid[0][0]==1)return 0; dp[0][0]=1; for(int i=1;i<m;i++){ if(obstacleGrid[0][i]==0) dp[0][i] = dp[0][i-1]; else dp[0][i] = 0; } for(int i=1;i<n;i++){ if(obstacleGrid[i][0]==0) dp[i][0] = dp[i-1][0]; else dp[i][0] = 0; } for(int i=1;i<n;i++){ for(int j =1;j<m;j++){ if(obstacleGrid[i][j]==0){ if(obstacleGrid[i-1][j]==0) dp[i][j] = dp[i-1][j]+dp[i][j]; if(obstacleGrid[i][j-1]==0) dp[i][j] = dp[i][j-1]+dp[i][j]; }else dp[i][j] = 0; } } return dp[n-1][m-1]; } };