| 23 | |
| 24 | |
| 25 | int cutRod(vector<int>& price,int N) { |
| 26 | |
| 27 | vector<int> cur (N+1,0); |
| 28 | |
| 29 | for(int i=0; i<=N; i++){ |
| 30 | cur[i] = i*price[0]; |
| 31 | } |
| 32 | |
| 33 | for(int ind=1; ind<N; ind++){ |
| 34 | for(int length =0; length<=N; length++){ |
| 35 | |
| 36 | int notTaken = 0 + cur[length]; |
| 37 | |
| 38 | int taken = INT_MIN; |
| 39 | int rodLength = ind+1; |
| 40 | if(rodLength <= length) |
| 41 | taken = price[ind] + cur[length-rodLength]; |
| 42 | |
| 43 | cur[length] = max(notTaken,taken); |
| 44 | } |
| 45 | } |
| 46 | |
| 47 | return cur[N]; |
| 48 | } |
| 49 | |
| 50 | |
| 51 |