931. 下降路径最小和【中等】
题解- 状态定义：dp[r][c]表示从位置为 (r, c) 的元素开始的下降路径最小和。
- 状态转移方程：dp[r][c] = matrix[r][c] + min(dp[r-1][c-1], dp[r-1][c], dp[r-1][c+1])，上一行三个位置中的下降路径最小和+本元素的值
- 初始条件：dp[0][j]=matirx[0][j]
- 返回值：min(dp[n-1][j])
class Solution {
public int minFallingPathSum(int[][] matrix) {
int n=matrix.length;
//dp初始化
int dp[][]=new int[n][n];
for(int i=0;i
for(int j=0;j
dp[i][j]=matrix[i][j];
//最左
if(j==0)
dp[i][j]+=Math.min(dp[i-1][j],dp[i-1][j+1]);
//最右
else if(j==n-1)
dp[i][j]+=Math.min(dp[i-1][j-1],dp[i-1][j]);
//其他
else
dp[i][j]+=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i-1][j+1]));
}
}
int min=100*n+1;
for(int i=0;i
时间复杂度：
O
(
n
2
)
O(n^2)
O(n2)
空间复杂度：
O
(
n
2
)
O(n^2)
O(n2)
优化
dp本行只与上一行有关，用滚动数组优化空间复杂度为O(n)
class Solution {
public int minFallingPathSum(int[][] matrix) {
int n=matrix.length;
//初始化
int pre[]=new int[n];//上一行
for(int i=0;i
int cur[]=new int[n];//本行
for(int j=n-1;j>=0;j--){
cur[j]=matrix[i][j];
//最左
if(j==0)
cur[j]+=Math.min(pre[j],pre[j+1]);
//最右
else if(j==n-1)
cur[j]+=Math.min(pre[j-1],pre[j]);
//其他
else
cur[j]+=Math.min(pre[j-1],Math.min(pre[j],pre[j+1]));
}
pre=cur;
}
int min=100*n+1;
for(int i=0;i
时间复杂度：
O
(
n
2
)
O(n^2)
O(n2)
空间复杂度：
O
(
n
)
O(n)
O(n)
进一步优化
不需要额外的空间，直接通过 修改原数组 记录路径最小和
class Solution {
public int minFallingPathSum(int[][] matrix) {
int n=matrix.length;
//动态规划 原地修改矩阵
for(int i=1;i
for(int j=n-1;j>=0;j--){
//最左
if(j==0)
matrix[i][0]+=Math.min(matrix[i-1][j],matrix[i-1][j+1]);
//最右
else if(j==n-1)
matrix[i][n-1]+=Math.min(matrix[i-1][j-1],matrix[i-1][j]);
//其他
else
matrix[i][j]+=Math.min(matrix[i-1][j-1],Math.min(matrix[i-1][j],matrix[i-1][j+1]));
}
}
int min=100*n+1;
for(int i=0;i
时间复杂度：
O
(
n
2
)
O(n^2)
O(n2)
空间复杂度：
O
(
1
)
O(1)
O(1)
题目2
120. 三角形最小路径和【中等】
题解
和上一题几乎一模一样，只是矩阵变成三角了
在矩阵空间复杂度为O(n)的解法上面做了进一步优化，由于在三角形中dp[i][j]的值只与dp[i-1][j-1]和dp[i-1][j]有关，因此可以只使用一个数组，而不是滚动数组来记录上一行的值，与昨天杨辉三角 II的进一步优化的解法相同
class Solution {
public int minimumTotal(List> triangle) {
int n=triangle.size();
int[] dp=new int[n];
dp[0]=triangle.get(0).get(0);
for(int i=1;i
for(int j=i;j>=0;j--){
int num=triangle.get(i).get(j);
if(j==0) num+=dp[0];
else if(j==i) num+=dp[j-1];
else num+=Math.min(dp[j-1],dp[j]);
dp[j]=num;
}
}
int min=10000*n+1;
for(int i=0;i
min=Math.min(min,dp[i]);
}
return min;
}
}
时间复杂度：
O
(
n
2
)
O(n^2)
O(n2)
空间复杂度：
O
(
n
)
O(n)
O(n)
优化
直接修改原数组，空间复杂度优化为O(1)
class Solution {
public int minimumTotal(List> triangle) {
int n=triangle.size();
for(int i=1;i
for(int j=0;j<=i;j++){
int num=triangle.get(i).get(j);
//最左
if(j==0)
num+=triangle.get(i-1).get(0);
//最右
else if(j==i)
num+=triangle.get(i-1).get(j-1);
//其他
else
num+=Math.min(triangle.get(i-1).get(j-1),triangle.get(i-1).get(j));
triangle.get(i).set(j,num);
}
}
int min=10000*n+1;
for(int i=0;i
min=Math.min(min,triangle.get(n-1).get(i));
}
return min;
}
}
时间复杂度：
O
(
n
2
)
O(n^2)
O(n2)
空间复杂度：
O
(
1
)
O(1)
O(1)
