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

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

为什么二维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;
    }
};
展开全部 4 讨论