三角形最小路径和
解题思路见:
https://leetcode.cn/problems/triangle/solutions/329143/san-jiao-xing-zui-xiao-lu-jing-he-by-leetcode-solu/
可以看下官方解题思路
方法一:动态规划
-
思路与算法
思路与算法.png -
细节
细节.png Javascript实现
/**
* @param {number[][]} triangle
* @return {number}
*/
var minimumTotal = function(triangle) {
let n = triangle.length
let f=[...triangle]
f[0][0]=parseInt(triangle[0][0])
for(let i=1;i<n;i++){
f[i][0]=f[i-1][0]+parseInt(triangle[i][0])
for(let j=1;j<i;j++){
f[i][j]=Math.min(f[i-1][j-1],f[i-1][j])+parseInt(triangle[i][j])
}
f[i][i]=f[i-1][i-1]+triangle[i][i]
}
let minTotal=f[n-1][0]
for(let i=1;i<n;i++){
minTotal=Math.min(minTotal,f[n-1][i])
}
return minTotal
};
复杂度分析:
- 时间复杂度:O(n^2) 其中 nnn 是三角形的行数。
- 空间复杂度:O(n^2) 我们需要一个 n∗n的二维数组存放所有的状态。
方法二:动态规划 + 空间优化
-
思路与算法👇
动态规划 + 空间优化 思路与算法.png Javascript实现
/**
* @param {number[][]} triangle
* @return {number}
*/
var minimumTotal = function(triangle) {
let n = triangle.length
let f=[...triangle.slice(0,2)]
console.log(f)
f[0][0]=parseInt(triangle[0][0])
for(let i=1;i<n;i++){
let curr = i % 2
let prev = 1 - curr
f[curr][0]=f[prev][0]+parseInt(triangle[i][0])
for(let j=1;j<i;j++){
f[curr][j]=Math.min(f[prev][j-1],f[prev][j])+parseInt(triangle[i][j])
}
f[curr][i]=f[prev][i-1]+triangle[i][i]
console.log(f)
}
console.log(f)
let minTotal=f[(n-1)%2][0]
for(let i=1;i<n;i++){
minTotal=Math.min(minTotal,f[(n-1)%2][i])
}
return minTotal
};
-
继续优化!
如何继续优化?使用的空间从2n变成n.png Javascript实现
/**
* @param {number[][]} triangle
* @return {number}
*/
var minimumTotal = function(triangle) {
let n = triangle.length
let f=[...triangle.slice(-1)]
console.log('f初始值',f)
f[0]=parseInt(triangle[0][0])
for(let i=1;i<n;i++){
f[i]=f[i-1]+parseInt(triangle[i][i])
for(let j=i-1;j>0;j--){
f[j]=Math.min(f[j-1],f[j])+parseInt(triangle[i][j])
}
f[0]=f[0]+triangle[i][0]
console.log(f)
}
console.log('f最终值',f)
let minTotal=f[0]
for(let i=1;i<n;i++){
minTotal=Math.min(minTotal,f[i])
}
return minTotal
};
/**
* @param {number[][]} triangle
* @return {number}
*/
var minimumTotal = function(triangle) {
let row = triangle.length
let dp=new Array(row)
// console.log(dp)
dp[0]=triangle[0][0]
for(let r=1;r<row;r++){
dp[r]=dp[r-1]+triangle[r][r]
for(let c=r-1;c>0;c--){
dp[c]=Math.min(dp[c],dp[c-1])+triangle[r][c]
}
dp[0]=dp[0]+triangle[r][0]
// console.log(dp)
}
let min = dp[0]
for(let i=1;i<dp.length;i++){
min=Math.min(min,dp[i])
}
// console.log(min)
return min
};