C++ dp 0ms


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

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.