Day 29: Dynamic Programming, DP

这是什麽

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 题目的创意性,要到 MediumHard 就能变化性了。


<<:  Day27 语法改革!零基础新手也能读懂的JS - JS30-01 Drum Kit

>>:  粗略的HDR理解

Deserialization

JSON serialization/deserialization 应该是不少 Android a...

[DAY-07] 强化人才密度 拿出业界最高薪资

从 WFH 的 三个半月多 ( 2021- 05, 06, 07, 08) 再回到 办公室 &am...

[D03] test

Day 03 连假先发一下。晚点编辑 END ...

Day17:【技术篇】SQL之其它常用语法

一、前言   上一篇文章有稍微带到简单的SQL基本CRUD操作方式,但实际玩起来我觉得就和GIT一样...

[Day25] Flutter GetX API AnimatedSwitcher

上一篇介绍了Shimmer这个第三方 并建立了自己想要的Widget 这一篇将实际结合API fet...