Memoization + Divide and Conquer = Dynamic Programming
动态规划的目的,是藉由记忆体储存计算结果来改善分治法的执行时间。
动态规划的步骤是:
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 就能变化性了。
<<: Day27 语法改革!零基础新手也能读懂的JS - JS30-01 Drum Kit
JSON serialization/deserialization 应该是不少 Android a...
从 WFH 的 三个半月多 ( 2021- 05, 06, 07, 08) 再回到 办公室 &am...
Day 03 连假先发一下。晚点编辑 END ...
一、前言 上一篇文章有稍微带到简单的SQL基本CRUD操作方式,但实际玩起来我觉得就和GIT一样...
上一篇介绍了Shimmer这个第三方 并建立了自己想要的Widget 这一篇将实际结合API fet...