本文共 1649 字，大约阅读时间需要 5 分钟。

解决方案

这个问题可以分为两个部分解决：寻找网格中从左上角到右下角的最小路径和，以及找出数组中的最大子串和。

1. 网格中的最小路径和

我们使用动态规划来解决网格问题。每个点的最短路径和只能来自于左边或上方，因此我们创建一个二维数组dp来记录每个点的最短路径和。

• 初始化：dp[0][0]为网格顶点的值。
• 边界处理：
  • 左边界（i=0，j>0）：dp[0][j] = dp[0][j-1] + grid[0][j]
  • 上边界（i>0，j=0）：dp[i][0] = dp[i-1][0] + grid[i][0]
• 中间点（i>0，j>0）：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

最后，dp[m-1][n-1]即为右下角的最小路径和。

2. 数组中的最大子串和

同样使用动态规划：

• 初始化：maxans和max都为数组的第一个元素。
• 遍历数组：每一步计算当前子串和，更新最大值。
• max是当前子串和与单独当前元素的最大值。
• maxans是遍历过程中的最大值。

代码实现

public class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        if (m == 0) return 0;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        
        dp[0][0] = grid[0][0];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) continue;
                if (i == 0) {
                    dp[i][j] = dp[i][j - 1] + grid[i][j];
                } else if (j == 0) {
                    dp[i][j] = dp[i - 1][j] + grid[i][j];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
    
    public static int maxSubArray(int[] nums) {
        if (nums.length == 0) return 0;
        int maxans = nums[0];
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            max = Math.max(nums[i], max + nums[i]);
            maxans = Math.max(maxans, max);
        }
        return maxans;
    }
}

总结

• 网格问题：通过动态规划填充dp数组，处理每个点的上下左右情况，最后返回右下角的值。
• 最大子串和：同样使用动态规划，记录当前子串和和最大值，确保每一步都取最优解。

这两个算法分别解决了两个不同的问题，展示了动态规划在不同场景中的应用。

转载地址：http://nlyk.baihongyu.com/