198. House Robber

💡 に答える

var rob = function (nums) {
  let dp = [];

  if (nums.length === 1) return nums[0];

  dp[0] = nums[0];
  dp[1] = Math.max(nums[0], nums[1]);

  for (let i = 2; i < nums.length; i++) {
    // i번째 집을 털었을 때 가질 수 있는 돈의 최댓값 = dp[i]
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
  }

  // console.log(dp);
  return dp[dp.length - 1];
};

📝 整理する

基本DP問題と見なすことができる.DPの他の方法のgreedyを除いて...?swap? two pointers? もう一つの方法は私がはっきりしていません(もっと簡単です)、その方法はまだ分かりませんので、ここには書いていません.
問題の要求を見てください.君は泥棒だ.隣の家のお金を盗むと警察に通報されるので、警察に通報されない場合、最も多くのお金を盗む額はいくらですか?そう聞いたのです.回答は次のとおりです.

最低価格のdp配列を含む最初のインデックスは、次のように決定されます.dp[0] = nums[0];

i 1軒目の家を強奪したときに得られるお金の最高値=dp[i].

この点を考慮すると、隣接する家は盗むことができず、dp[i - 1], dp[i - 2] + nums[i]、すなわちdp[i-1]とdp[i-2] + nums[i]の中で、より大きな価格が最も価値がある.

修正、指摘を歓迎します!

質問リンク

https://leetcode.com/problems/house-robber/

LeetCode GitHub

https://github.com/tTab1204/LeetCode