leetcode 198. House Robber [Medium]

題目敘述

看題目直覺想到是 dp 的題型，在一維陣列中取 n 個不相鄰的數字，使其有最大的總和。

這題算是基本的 dp 題型，本身不難想，底下的解答還能優化成使用 2 個變數去紀錄狀態。

解題紀錄

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


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];
   }
};