CutRodDp solve the same problem using dynamic programming
(price []int, length int)
| 21 | |
| 22 | // CutRodDp solve the same problem using dynamic programming |
| 23 | func CutRodDp(price []int, length int) int { |
| 24 | r := make([]int, length+1) // a.k.a the memoization array |
| 25 | r[0] = 0 // cost of 0 length rod is 0 |
| 26 | |
| 27 | for j := 1; j <= length; j++ { // for each length (subproblem) |
| 28 | q := -1 |
| 29 | for i := 1; i <= j; i++ { |
| 30 | q = Max(q, price[i]+r[j-i]) // avoiding recursive call |
| 31 | } |
| 32 | r[j] = q |
| 33 | } |
| 34 | |
| 35 | return r[length] |
| 36 | } |
| 37 | |
| 38 | /* |
| 39 | func main() { |