首页 > itarticle > algorithm

algorithm

admin 11月 14, 2020 0

Minimum Path Sum

Title Detail

Given an integer array A, you partition the array into (contiguous) subarrays of length at most K. After partitioning, each subarray has their values changed to become the maximum value of that subarray.

Return the largest sum of the given array after partitioning.

Example 1:

1
2
3

Input: A = [1,15,7,9,2,5,10], K = 3
Output: 84
Explanation: A becomes [15,15,15,9,10,10,10]

Note:

1 2	1 <= K <= A.length <= 500 0 <= A[i] <= 10^6

思路

动态规划问题。

用原来的grid矩阵存储路径和
注意三种特殊情况，即矩阵初始位置、顶栏及左侧栏和求解。

初始：grid[0][0] = grid[0][0]

顶栏：grid[i][j] = grid[i][j-1]

左侧栏：grid[i][j] = grid[i-1][j]
其余位置：grid[i][j] = min(grid[i][j-1], grid[i-1][j])

Algorithm

class  {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        for(int i=0; i<m;i++){
            for(int j=0; j<n; j++){
                if(i==0&&j==0){
                    continue;
                }
                else if(i==0&&j!=0){
                    grid[i][j] += grid[i][j-1]; 
                }
                else if(j==0&&i!=0){
                    grid[i][j] += grid[i-1][j];
                }else{
                    grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
                }
            }
        }
        return grid[m-1][n-1];
    }
}