LeetCode <dp>120&931 Triangle&Minimum Falling Path Sum
原创LeetCode <dp>120&931 Triangle&Minimum Falling Path Sum
原创
120. Triangle
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
题目大意：找到最小的路径，使得和最小。
解法一：
记忆化搜索法。
int mem [][] ;
public int minimumTotal(List<List<Integer>> triangle) {
if (triangle == null || triangle.size()==0) return 0;
mem = new int[triangle.size()][triangle.get(triangle.size()-1).size()];
return minimumTotal_recursion(triangle,0,0);
}
public int minimumTotal_recursion(List<List<Integer>> triangle,int row ,int col){
if (triangle == null || triangle.size()==0) return 0;
if (row == triangle.size()-1 ) return triangle.get(row).get(col); //&& col == triangle.get(triangle.size()-1).size()-1
if (mem[row][col] == 0)
mem[row][col] = triangle.get(row).get(col) +Math.min( minimumTotal_recursion(triangle,row+1,col), minimumTotal_recursion(triangle,row+1,col+1));
return mem[row][col];
}解法二：
动态规划法。
public int minimumTotal(List<List<Integer>> triangle) {
int n =triangle.size();
int[] dp = new int[n+1];
for (int i = n-1;i>=0;i--){
for (int j=0;j<=i;j++){
dp[j] = Math.min(dp[j],dp[j+1])+triangle.get(i).get(j);
}
}
return dp[0];
}
解法三：
public int minimumTotal(List<List<Integer>> triangle) {
int res = Integer.MAX_VALUE;
if (triangle == null || triangle.size()==0) return 0;
int[] dp = new int[triangle.get(triangle.size()-1).size()] ;
dp[0]=triangle.get(0).get(0);
for (int i =1;i<triangle.size();i++){
int [] temp = dp.clone();
for (int j = 0;j<=i;j++){
if (j==0) dp[j] = triangle.get(i).get(j)+ temp[j];
else if (j==i) dp[j] = triangle.get(i).get(j) + temp[j-1];
else dp[j] = triangle.get(i).get(j) + Math.min(temp[j],temp[j-1]);
}
}
for (int x:dp){
res = Math.min(res,x);
}
return res;
}931. Minimum Falling Path Sum
Given a square array of integers A, we want the minimum sum of a falling path through A.
A falling path starts at any element in the first row, and chooses one element from each row. The next row's choice must be in a column that is different from the previous row's column by at most one.
Example 1:
Input: [[1,2,3],[4,5,6],[7,8,9]]
Output: 12
Explanation:
The possible falling paths are:[1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9][2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9][3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9]
The falling path with the smallest sum is [1,4,7], so the answer is 12.
Note:
1 <= A.length == A[0].length <= 100-100 <= A[i][j] <= 100
题目大意：找到最小的路径，使得和最小。
解法：
public int minFallingPathSum(int[][] A) {
if (A ==null||A.length==0) return 0;
int[] memo = A[0].clone();
int res = Integer.MAX_VALUE;
for (int i =1;i<A.length;i++){
int[] temp = memo.clone();
for (int j = 0;j<A[0].length;j++){
if (j == 0) {
memo[j] = A[i][j] + Math.min(temp[j],temp[j+1]);
}else if (j==A[0].length-1) {
memo[j] = A[i][j] + Math.min(temp[j],temp[j-1]);
}else {
memo[j] = A[i][j] + mymin(temp[j],temp[j+1],temp[j-1]);
}
}
}
for (int i = 0;i<A[0].length;i++){
res = Math.min(res,memo[i]);
}
return res;
}
public int mymin(int a,int b,int c){
return Math.min(Math.min(a,b),c);
}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。