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项且时间是tdp[i-1][t-1] t * satisfaction[i-1]不选择第i项dp[i-1][t]方案1Codeclass Solution { public: unordered_mapint, int ump; int n; int dfs(vectorint 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(vectorint satisfaction) { n satisfaction.size(); sort( satisfaction.begin(), satisfaction.end() ); if(satisfaction.back() 0) return 0; int r dfs(satisfaction, 0, 1); return r; } };方案2动态规划Codeclass Solution {public:int n;int maxSatisfaction(vector satisfaction) {n satisfaction.size();sort( satisfaction.begin(), satisfaction.end() );if(satisfaction.back() 0) return 0;vectorvector dp(n1, vector(n1, INT_MIN/10));for(int i 0; in ;i) dp[i][0] 0;for(int i 1; in ;i) {for(int t1; ti; 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());}};