题目描述：
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
今日学习：
1.多维数组的深拷贝
2.动规真神奇啊
题解：
1.我自己琢磨的，比较复杂的dfs，不知道问什么在leetcode中通不过，在控制台测试几个成功了，不过肯定会超时
2.普通dfs，超时
3.记忆化搜索+dfs
4.bfs
5.自底向上的动规
6.直接用原数组动规
7.一维动规
/**
* @param {number[][]} triangle
* @return {number}
*/
//首先能想到DFS
//在控制台是正确的输出11，在leetcode中输出2，不明白哪里出问题了
var minimumTotal = function(triangle) {
if(triangle.length == 0) return 0
if(triangle.length == 1) return triangle[0][0]
let sum = triangle[0][0]
let lt = copyArr(triangle), rt = copyArr(triangle)
lt.shift(), rt.shift()
for(let i = 0; i < lt.length; i++) {
lt[i].pop()
rt[i].shift()
}
return sum + Math.min(minimumTotal(lt), minimumTotal(rt))
};
var copyArr = function(obj) {
var out = []
i = 0
len = obj.length
for (; i < len; i++) {
if (obj[i] instanceof Array) {
out[i] = copyArr(obj[i])
} else {
out[i] = obj[i]
}
}
return out
}
//简洁版dfs，但是会超时
var minimumTotal = function(triangle) {
let limit = triangle.length;
let helper = function(i,j){
if((i+1) == limit) return triangle[i][j];
return Math.min(helper(i+1,j),helper(i+1,j+1))+triangle[i][j];
}
return helper(0,0);
};
//加缓存的dfs
var minimumTotal = function(triangle) {
const res = []
const n = triangle.length
const memo = new Array(n).fill().map(() => [])
return reversionByMemo(0, 0, triangle, memo)
}
function reversionByMemo(i, j, triangle, memo) {
if (i >= triangle.length-1) {
return triangle[i][j]
}
if (memo[i][j]) return memo[i][j]
const left = reversionByMemo(i+1, j, triangle, memo)
const right = reversionByMemo(i+1, j+1, triangle, memo)
memo[i][j] = Math.min(left, right) + triangle[i][j]
return memo[i][j]
}
//BFS
var minimumTotal = function(triangle) {
let space = triangle[0].slice(0), min = Infinity
for(let i=1; i < triangle.length; ++i) {
let last = space.slice(0)
space.length = triangle[i].length;
space.fill(Infinity)
for(let j=0; j < last.length; ++j) {
space[j] = Math.min(last[j] + triangle[i][j], space[j])
space[j + 1] = Math.min(last[j] + triangle[i][j + 1], space[j + 1])
}
}
// 找到最后一层中，路径最短的
return min = Math.min(...space)
};
//动规
var minimumTotal = function(triangle) {
var dp = triangle;
for(var i = dp.length-2;i >= 0;i--){
for(var j = 0;j < dp[i].length;j++){
dp[i][j] = Math.min(dp[i+1][j],dp[i+1][j+1]) + dp[i][j];
}
}
return dp[0][0];
};
//直接用原数组动规
var minimumTotal = function(triangle) {
for(var i = triangle.length-2;i >= 0;i--){
for(var j = 0;j < triangle[i].length;j++){
triangle[i][j] = Math.min(triangle[i+1][j],triangle[i+1][j+1]) + triangle[i][j];
}
}
return triangle[0][0];
};
//一维动规
var minimumTotal = function(triangle) {
var dp = new Array(triangle.length+1).fill(0);
for(var i = triangle.length-1;i >= 0;i--){
for(var j = 0;j < triangle[i].length;j++){
dp[j] = Math.min(dp[j],dp[j+1]) + triangle[i][j];
}
}
return dp[0];
};