打家劫舍 经典动态规划
我之前写的
var arr = [1, 5, 1, 120, 100, 1000, 10000,1000,50];
var dp = new Array(arr.length).fill(0);
dp[0] = arr[0];
dp[1] = arr[1];
let max=dp[1]
for (let j = 2; j < dp.length; j++) {
for (let i = 2; i <= j; i++) {
dp[j] = Math.max(dp[i - 2] + arr[j], dp[i]);
}
max=Math.max(dp[i],max)
}
console.log(dp[l - 1], dp,max);
过后写的
var dp = new Array(arr.length).fill(0);
dp[0] = arr[0];
dp[1] = arr[1];
let max = Math.max(dp[0], dp[1]);
for (let j = 2; j < dp.length; j++) {
dp[j] = Math.max(dp[j - 2] + arr[j], dp[j-1]);
}
console.log(dp);
总结原因: 以前想的是dp里面元素保存的是该元素最大的值 过后想通了 该元素直接保存该位置的最大结果 我靠啊啊啊
|