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

2023-12-29 10:29:41

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

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

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

?

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

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

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

?

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

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

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

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

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

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

?

文章来源:https://blog.csdn.net/summer_fish/article/details/135283135
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。