动态规划中的状态转移方程和最优子结构_动态规划的转移方程

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];
}

这道题中，有一个最小路径总和，也就是有一个最优解。像这样，我们可以通过计算子问题的最优解可以来构建整个问题的最优解，我们就说这个问题具有最优子结构，即满足最优性原理。

你甚至不需要看懂这道题答案的具体代码，只需要你能理解啥是状态转移方程和最优子结构。

能采用动态规划求解的问题的一般要具有以下性质：

• 具有最优子结构：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优性原理。

• 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。

总结出动态规划法在实际应用中简化的步骤：

• 分析最优解的性质，并刻画其结构特征

• 递归的定义最优解，得到状态转移方程/递推关系式【难点】

• 以自底向上方式计算出最优值【填表】

• 根据计算最优值时得到的信息，构造问题的最优解【可选】，这里的第四步，构造问题的最优解，不是必须的，但是有一些题目需要。

动态规划法是一种用空间换时间的技术，本质上是一种比较 “聪明” 的枚举法。