leetcode 198. House Robber [Medium]

題目敘述

看題目直覺就是 DP：在一維陣列中選取若干個不相鄰的數字，使總和最大。

這題是基本的 DP 題型，狀態轉移不難推導，下面的解法還可以進一步優化成只用兩個變數來記錄狀態。

解題紀錄

class Solution {
public:
   int rob(vector<int>& nums) {
       if (nums.size() == 1) return nums[0];
       
       int dp[100] = {0};
       dp[0] = nums[0];
       dp[1] = max(nums[0], nums[1]);
       
       for (int i = 2; i < nums.size(); ++i) {
           dp[i] = max(dp[i-1], dp[i-2]+nums[i]);
       }
       return dp[nums.size()-1];
   }
};