Algorithm--Minimum path sum
Dynamic Programming
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
1 | class Solution { |
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 孙云增的博客!
评论