Untitled
unknown
plain_text
a year ago
752 B
1
Indexable
Never
class Solution { //01 knapsack public: int solve(int i,int end,vector<int>&slices,int n,vector<vector<int>>&dp){ // n -no of slices i can take if(n==0 || i>end) return 0; if(dp[i][n]!=-1) return dp[i][n]; int include= slices[i] +solve(i+2,end,slices,n-1,dp); int exclude= solve(i+1,end,slices,n,dp); return dp[i][n]=max(include,exclude); } int maxSizeSlices(vector<int>& slices) { int n=slices.size(); vector<vector<int>> dp(n,vector<int>(n,-1)); vector<vector<int>> dp2(n,vector<int>(n,-1)); int c1=solve(0,slices.size()-2,slices,n/3,dp); int c2=solve(1,slices.size()-1,slices,n/3,dp2); return max(c1,c2); } };