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
记得前面讲过,Storyboard 里面可以放置多个页面(ViewController),页面之间的...
前言 list 是 Python 中最常见的资料类型,有许多的应用都会用到 list 喔! 今天会先...
今日目标 上篇仅介绍如何将数值转换为 Numpy array 的方法与其中的使用方式,这边要来提一下...
集合其实和阵列有些相似,阵列是将相同资料型态的资料收集起来,而集合是收集一群相关资料,再以特定的类别...
Student再加上age属性,加default是因为我已经有了数据 记得执行迁移 现在的资料库 有...