切钢条问题

package program

import (
    "fmt"
    "testing"
)

func TestCutPrice(t *testing.T) {
    p := []int{0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30}
    fmt.Println(cutPrice(p, 4))
}

func cutPrice(p []int, n int) int {
    dp := make([]int, len(p))
    dp[0] = p[0]
    for j := 1; j <= n; j++ {
        q := 0
        for i := 1; i <= j; i++ {
            q = max(q, p[i]+dp[j-i])
        }
        dp[j] = q
    }
    return dp[n]
}