資訊專欄INFORMATION COLUMN
摘要：注意對(duì)邊界條件的判斷，是否非空，是否長(zhǎng)度為
House Robber I Problem
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.
ExampleGiven [3, 8, 4], return 8.
Note注意對(duì)邊界條件的判斷，是否非空，是否長(zhǎng)度為1.
Solutionclass Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
int n = nums.length;
int[] dp = new int[n];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]);
}
return dp[n-1];
}
}
Update 2018-9
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int n = nums.length;
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = nums[0];
for (int i = 2; i <= n; i++) {
dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i-1]);
}
return dp[n];
}
}
House Robber II
Problem
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, 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: [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),
because they are adjacent houses.
Example 2:
Input: [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.
Solution
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int n = nums.length;
if (n == 1) return nums[0];
int[] dp = new int[n+1];
//rob head
dp[0] = 0;
dp[1] = nums[0];
for (int i = 2; i < n; i++) {
dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i-1]);
}
//save head-robbed result to temp
int temp = dp[n-1];
//not rob head
dp[0] = 0;
dp[1] = 0;
for (int i = 2; i <= n; i++) {
dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i-1]);
}
//return the larger of tail-robbed and head-robbed
return Math.max(dp[n], temp);
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/65556.html
摘要：因?yàn)槿×岁?duì)首就不能取隊(duì)尾，所以對(duì)數(shù)組循環(huán)兩次，一個(gè)從取到，一個(gè)從取到，比較兩次循環(huán)后隊(duì)尾元素，取較大者。注意，要先討論當(dāng)原數(shù)組位數(shù)小于時(shí)的情況。 Problem After robbing those houses on that street, the thief has found himself a new place for his thievery so that he wi...
摘要：你不能連著偷兩家因?yàn)檫@樣會(huì)觸發(fā)警報(bào)系統(tǒng)?，F(xiàn)在有一個(gè)數(shù)組存放著每一家中的可偷金額，問(wèn)可以偷的最大金額為多少這里考驗(yàn)了動(dòng)態(tài)編程的思想。動(dòng)態(tài)編程要求我們將問(wèn)題一般化，然后再找到初始情況開(kāi)始這個(gè)由一般到特殊的計(jì)算過(guò)程。 House Robber I You are a professional robber planning to rob houses along a street. Each...
摘要：動(dòng)態(tài)規(guī)劃復(fù)雜度時(shí)間空間思路一般來(lái)說(shuō)，給定一個(gè)規(guī)則，讓我們求任意狀態(tài)下的解，都是用動(dòng)態(tài)規(guī)劃。另外我們可以做一點(diǎn)優(yōu)化，本來(lái)我們是要用一個(gè)數(shù)組來(lái)保存之前的結(jié)果的。所以我們分別算出這兩個(gè)條件下的最大收益，然后取更大的就行了?？梢詮?fù)用的代碼。 House Robber I You are a professional robber planning to rob houses along a ...
摘要：復(fù)雜度思路對(duì)于每一個(gè)位置來(lái)說(shuō)，考慮兩種情況分別對(duì)和再進(jìn)行計(jì)算。用對(duì)已經(jīng)計(jì)算過(guò)的進(jìn)行保留，避免重復(fù)計(jì)算。 LeetCode[337] House Robber III The thief has found himself a new place for his thievery again. There is only one entrance to this area, calle...
摘要：前言從開(kāi)始寫(xiě)相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒(méi)有按順序?qū)懍F(xiàn)在翻起來(lái)覺(jué)得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個(gè)索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開(kāi)始寫(xiě)leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒(méi)有按順序?qū)憽F(xiàn)在翻起來(lái)覺(jué)得蠻亂的。可能大家看著也非常不方便。所以在這里做個(gè)索引嘻嘻。 順序整理 1~50 1...
閱讀 3008·2023-04-26 02:22
閱讀 2355·2021-11-17 09:33
閱讀 3251·2021-09-22 16:06
閱讀 1164·2021-09-22 15:54
閱讀 3599·2019-08-29 13:44
閱讀 2021·2019-08-29 12:37
閱讀 1376·2019-08-26 14:04
閱讀 1977·2019-08-26 11:57
