文章目錄
- 1. 題目來源
- 2. 題目決議
1. 題目來源
鏈接：879. 盈利計劃
相關：
- [背包] 背包問題演算法模板(模板)
- [01背包] 潛水員(01背包+二維費用背包+思維)
2. 題目決議
將問題抽象成二維費用背包求方案數是最難的，
抽象完了還有狀態定義、初始化、三維變二維的細節需要考慮，
本題在第三維狀態定義中使用了 >= 這個定義，這個就牽扯到負數下標問題，因為 >=-1 也會包含有正確情況，也得進行狀態轉移，
具體看手寫筆記：
時間復雜度： O ( n 3 ) O(n^3) O(n3)
空間復雜度： O ( n 2 ) O(n^2) O(n2)
class Solution {
public:
int profitableSchemes(int n, int m, vector<int>& group, vector<int>& profit) {
const int MOD = 1e9+7;
vector<vector<int>> f(n + 1, vector<int>(m + 1));
for (int i = 0; i <= n; i ++ ) f[i][0] = 1;
for (int i = 0; i < group.size(); i ++ ) { // 列舉任務
int g = group[i], p = profit[i];
for (int j = n; j >= g; j -- ) // 列舉人
for (int k = m; k >= 0; k -- ) // 列舉利潤
f[j][k] = (f[j][k] + f[j - g][max(0, k - p)]) % MOD;
}
return f[n][m];
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/286698.html
標籤：其他