Untitled
plain_text
a month ago
820 B
0
Indexable
Never
#include<vector> long long int solve(vector<long long int>& arr,int i,vector<int> &dp){ if(i>=arr.size()) return 0; if (i == arr.size() - 1) return arr[i]; if(dp[i]!=-1) return dp[i]; int ans=max(solve(arr,i+1,dp),solve(arr,i+2,dp)+arr[i]); dp[i]=ans; return ans; } long long int houseRobber(vector<int>& valueInHouse) { vector< int> dp1(valueInHouse.size(),-1); vector< int> dp2(valueInHouse.size(),-1); vector< long long int> one; vector<long long int> two; if(valueInHouse.size()==1) return valueInHouse[0]; for(int i=0;i<valueInHouse.size()-1;i++) one.push_back(valueInHouse[i]); for(int i=1;i<valueInHouse.size();i++) two.push_back(valueInHouse[i]); return max(solve(one,0,dp1),solve(two,0,dp2)); }