leetcode 困难题 1402. Reducing Dishes 做菜顺序

Problem: 1402. Reducing Dishes 做菜顺序

两种方案的

方案1: 记忆化深度优先搜索，首先排序的， 然后对每一个数字，两种选择的，1选2不选，不选的话时间不变，选的话时间加一且需要累加time * satisfaction[index];，拿到两者的最大值

方案2: 动态规划的，dp[i][j]表示以satisfaction[i]结束且时间步是j的最大值，递推公式是：dp[i][t] = max(dp[i-1][t-1] + t * satisfaction[i-1], dp[i-1][t]);，也就是选择第i项且时间是t，dp[i-1][t-1] + t * satisfaction[i-1]，不选择第i项dp[i-1][t]

方案1Code

class Solution { public: unordered_map<int, int> ump; int n; int dfs(vector<int>& satisfaction, int index, int time) { if(index == n) return 0; int r1, r2, mx = 0, key = index * 1000 + time; if( ump.count(key) != 0 ) return ump[key]; r1 = dfs(satisfaction, index + 1, time); r2 = dfs(satisfaction, index + 1, time + 1) + time * satisfaction[index]; mx = max(r1, r2); ump[key] = mx; return mx; } int maxSatisfaction(vector<int>& satisfaction) { n = satisfaction.size(); sort( satisfaction.begin(), satisfaction.end() ); if(satisfaction.back() <= 0) return 0; int r = dfs(satisfaction, 0, 1); return r; } };

方案2动态规划Code

class Solution {
public:
int n;
int maxSatisfaction(vector& satisfaction) {
n = satisfaction.size();
sort( satisfaction.begin(), satisfaction.end() );
if(satisfaction.back() <= 0) return 0;
vector<vector> dp(n+1, vector(n+1, INT_MIN/10));
for(int i= 0; i<=n ;i++) dp[i][0] = 0;
for(int i= 1; i<=n ;i++) {
for(int t=1; t<=i; t++) {
dp[i][t] = max(dp[i-1][t-1] + t * satisfaction[i-1], dp[i-1][t]);
}
}
return *max_element(dp[n].begin(), dp[n].end());
}
};