class Solution{ public: int solve(int price[], int n , vector<int>& dp, int idx){ if( idx >= n) return 0; if(dp[idx] != -1) return dp[idx]; int ans = 0; for(int i = 1; i <= n - idx; i++){ ans = max(ans, price[i - 1] + solve(price, n , dp, idx + i)); } return dp[idx] = ans; } int cutRod(int price[], int n) { //code here vector<int> dp; dp.resize(n, -1); return solve( price,n, dp, 0); } };
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter