Problem: 198. 打家劫舍
題目描述
思路
1.定義狀態(tài)：dp[i]表示從第i個房子開始偷起可以偷得的最大金額數(shù)目；
2.狀態(tài)轉(zhuǎn)移：由于不能連續(xù)的偷相鄰的兩個房子，則為了使得從第i個房子開始偷起是最大金額則要判斷是從當(dāng)前第i個房子開始偷（代碼中表示為nums[i] + dp[i + 2]）,還是不偷當(dāng)前第i個房子，而是從第i + 1個房子開始偷（代碼中表示為dp[i + 1]）即最終得到dp[i] = max(dp[i + 1], nums[i] + dp[i + 2])
復(fù)雜度
時間復(fù)雜度:
O ( n ) O(n) O(n)；其中 n n n為數(shù)組nums的長度
空間復(fù)雜度:文章來源：http://www.zghlxwxcb.cn/news/detail-857411.html
O ( n ) O(n) O(n)文章來源地址http://www.zghlxwxcb.cn/news/detail-857411.html
Code
class Solution {
/**
* Get the maximum amount
*
* @param nums Given array(Store the amount of each house)
* @return int
*/
public int rob(int[] nums) {
int n = nums.length;
int[] dp = new int[n + 2];
for (int i = n - 1; i >= 0; --i) {
dp[i] = Math.max(dp[i + 1], nums[i] + dp[i + 2]);
}
return dp[0];
}
}
到了這里，關(guān)于力扣198. 打家劫舍的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
