LeetCode 64：给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。
这个问题的本质其实是一个背包问题。
把 i 设置为向下走，把 j 设置为向右走，从 (0，0) 走到 (i，j) 的最小路径总和置为f[i][j]。那么我们是怎么走到(i，j)的呢？有三种可能。
-
当前位置只能通过往下移动而来，即有f[i][j] = f[i-1][j] + grid[i][j]
-
当前位置只能通过往右移动而来，即有f[i][j] = f[i][j-1] + grid[i][j]
-
当前位置既能通过往下也能往右移动，为了使路径上的数字总和为最小，需要在向下和向右走之前取一个最小值，既有f[i][j] = min(f[i][j-1],f[i-1][j]) + grid[i][j]
像这样，当前阶段的状态往往是上一阶段状态和相应决策的结果，采用指标函数来表示它们之间的关系称为状态转移方程。
代码实现：
public static int minPathSum(int[][] grid) {int m = grid.length, n = grid[0].length;int[][] f = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (i == 0 && j == 0) {f[i][j] = grid[i][j];} else {//如果是第一行或第一列只需要考虑left或者top值//其余位置则需要选取left和top比较后较小的值int top = i - 1 >= 0 ? f[i - 1][j] + grid[i][j] : Integer.MAX_VALUE;int left = j - 1 >= 0 ? f[i][j - 1] + grid[i][j] : Integer.MAX_VALUE;f[i][j] = Math.min(top, left);}}}return f[m - 1][n - 1];
}这道题中，有一个最小路径总和，也就是有一个最优解。像这样，我们可以通过计算子问题的最优解可以来构建整个问题的最优解，我们就说这个问题具有最优子结构，即满足最优性原理。
你甚至不需要看懂这道题答案的具体代码，只需要你能理解啥是状态转移方程和最优子结构。
能采用动态规划求解的问题的一般要具有以下性质：
-
具有最优子结构：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优性原理。
-
有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。
总结出动态规划法在实际应用中简化的步骤：
-
分析最优解的性质，并刻画其结构特征
-
递归的定义最优解，得到状态转移方程/递推关系式【难点】
-
以自底向上方式计算出最优值【填表】
-
根据计算最优值时得到的信息，构造问题的最优解【可选】，这里的第四步，构造问题的最优解，不是必须的，但是有一些题目需要。
动态规划法是一种用空间换时间的技术，本质上是一种比较 “聪明” 的枚举法。
