這是什麼

Memoization + Divide and Conquer = Dynamic Programming

動態規劃的目的，是藉由記憶體儲存計算結果來改善分治法的執行時間。

動態規劃的步驟是：

1. 運用分治法拆解問題。
2. 處理問題前，檢查是否有處理結果，進而改變處理的過程。
3. 處理完畢後，儲存處理結果。
4. 等待小問題的處理結果，最後組裝成初始問題的答案。

刷題：198. House Robber

連結

題目

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
             Total amount you can rob = 2 + 9 + 1 = 12.

Constraints:

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 400

思考

這題講述，如果選擇搶第一家，那不能搶第二家，只能跳到第三家，因此，要比較是要搶這一家還是下一家。
有這概念後，可以用 DP 計算搶劫到這家時，最優化累積的金額。
計算完成後，比較最後兩家的金額，回傳最大者即可。

解題

JS

/**
 * @param {number[]} nums
 */
const rob = (nums) => {
  const n = nums.length;

  if (n === 0) {
    return 0;
  } else if (n === 1) {
    return nums[0];
  } else if (n === 2) {
    return Math.max(nums[0], nums[1]);
  }

  let totalAmount = new Array(n);
  totalAmount[0] = nums[0];
  totalAmount[1] = nums[1];
  totalAmount[2] = nums[0] + nums[2];

  for (let i = 3; i < n; i++) {
    totalAmount[i] = Math.max(totalAmount[i - 2], totalAmount[i - 3]) + nums[i];
  }

  return Math.max(totalAmount[n - 1], totalAmount[n - 2]);
};

Java

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;

        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return nums[0];
        } else if (n == 2) {
            return Math.max(nums[0], nums[1]);
        }

        int[] totalAmount = new int[n];
        totalAmount[0] = nums[0];
        totalAmount[1] = nums[1];
        totalAmount[2] = nums[0] + nums[2];

        for (int i = 3; i < n; i++) {
            totalAmount[i] = Math.max(totalAmount[i - 2], totalAmount[i - 3]) + nums[i];
        }

        return Math.max(totalAmount[n - 1], totalAmount[n - 2]);
    }
}

C

int max(int a, int b)
{
    if (a > b)
    {
        return a;
    }

    return b;
}

int rob(int *nums, int numsSize)
{
    if (numsSize == 0)
    {
        return 0;
    }
    else if (numsSize == 1)
    {
        return nums[0];
    }
    else if (numsSize == 2)
    {
        return max(nums[0], nums[1]);
    }

    int *totalAmount = calloc(numsSize, sizeof(int));
    totalAmount[0] = nums[0];
    totalAmount[1] = nums[1];
    totalAmount[2] = nums[0] + nums[2];

    for (int i = 3; i < numsSize; i++)
    {
        totalAmount[i] = max(totalAmount[i - 2], totalAmount[i - 3]) + nums[i];
    }

    return max(totalAmount[numsSize - 1], totalAmount[numsSize - 2]);
}

看法

這題算是蠻簡單的，因為題目有規律，所以容易寫出轉化成 DP 的程式碼。

題外話一下，這題的標題我一看到就笑了，搶劫可以用 DP 模擬最佳解，這在治安良好的台灣實在是很難想像，所以我腦海中浮現的畫面是遊戲 GTA ，不少任務要求玩家去搶劫...

結論

DP 困難的地方在於，能否看出規律，光是這點就不是件容易的事情。
這邊刷了一題 Easy，還看不太出來 DP 題目的創意性，要到 Medium 或 Hard 就能變化性了。