1402. 做菜顺序【DP】

题目

分析

// 输入：satisfaction = [-1,-8,0,5,-9]
// 首先应该排序，大的应该在后面(给更大的比重)
// [-9, (-8, -1, 0, 5)]
// 子序列这个的值取决于，前面选择了几个？dp[l][k]

代码

package main

import (
    "sort"
)

type DP [][]int
// 输入：satisfaction = [-1,-8,0,5,-9]
// 首先应该排序，大的应该在后面(给更大的比重)
// [-9, (-8, -1, 0, 5)]
// 子序列这个的值取决于，前面选择了几个？dp[l][k]
func maxSatisfaction(satisfaction []int) int {
    length := len(satisfaction)
    dp := make(DP, length, length)
    for i:=0; i<length; i++ {
        dp[i] = make([]int, length)
    }

    sort.Ints(satisfaction)
    return satisfy(satisfaction, dp, 0, 0)
}

func satisfy(satisfaction []int, dp DP, l, k int) int {
    if l>len(satisfaction)-1 {
        return 0
    }

    if dp[l][k] != 0 {
        return dp[l][k]
    }

    // 策略0：l不做
    dp[l][k] = satisfy(satisfaction, dp, l+1, k)

    // 策略1：l做
    case1 := satisfaction[l]*(k+1) + satisfy(satisfaction, dp, l+1, k+1)   // 作为初始值
    if case1 > dp[l][k] {
        dp[l][k] = case1
    }

    return dp[l][k]
}