讨论/题目交流/1402.做菜顺序/
1402.做菜顺序

image.png
这道题如果用dp来做,为什么是二维dp,dp的两个维度含义分别是什么

展开讨论
共 4 个讨论

二维dp是因为有两个状态:
第一个是当前是前i道菜
第二个是当前已做了j道菜
第一个是比较典型的dp状态,第二个是因为这个是和time这个量紧密相关的,你也可以理解为就是time
可以看我的题解
https://leetcode-cn.com/problems/reducing-dishes/solution/tan-xin-dong-tai-gui-hua-by-xjtupanda/

为什么二维dp,因为数据范围很小,很自然就会想到二维dp,不过一维dp也是可以的。
dp[i]表示花费i时间可以获得的最大值

class Solution {
public:
    int dp[505];
    int maxSatisfaction(vector<int>& satisfaction) {
        memset(dp,0x80,sizeof(dp));
        sort(satisfaction.begin(),satisfaction.end());
        dp[0] = 0;
        int n = satisfaction.size();
        for(int i=0;i<n;i++){
            for(int j=i;j>=0;j--){
                dp[j+1] = max(dp[j+1], satisfaction[i]*(j+1)+dp[j]);
            }
        }
        int ans = 0;
        for(int i=1;i<=n;i++)ans = max(ans,dp[i]);
        return ans;
    }
};

兄弟又见到你了

天皇问政

1