https://leetcode.com/problems/build-array-where-you-can-find-the-maximum-exactl
1420. Build Array Where You Can Find The Maximum Exactly K Comparisons
這題有給一段程式碼，就是給定一個array nums，更新最大值，如果當前nums[i] >
max_v
則cost + 1
然後求給定array長度為n，且每個element nums[i]的值介於1至m之間，cost正好為k的
arr
答案要mod 1e9 + 7
1<=n<=50, 1<=m<=100, 0<=k<=n
思路：
典型的DP題，定義memo[i][j][h]為當在第i個位置且i-1個 elements中最大值為j，
剩餘可用的cost為h的情況底下 最終能完成符合總cost為k的array總數
在此定義底下轉移方程可以寫成
memo[i][j][h] = j * memo[i+1][j][h] + sum( for c in [j+1, m]
memo[i+1][c][h+1])
第一項意思是當前nums[i]的值不超過j，所以當前位置有j個選擇
第二項就代表當前nums[i]大於j，所以可選擇的candidate就是從 range j+1到m取一
然後繼續從第i+1位置繼續往下遞迴 為了避免重複計算所以用memo來記 若已經走過直接回
傳就可
程式碼:
class Solution {
public:
long memo[51][101][51], mod = 1e9 + 7l;
long dp(int n, int m, int k, int i, int cm) {
if (k < 0) return 0l;
if (i == n)
return k ? 0l : 1l;
if (memo[i][cm][k] != -1) return memo[i][cm][k];
long ret = 0l;
for(int j=cm+1; j<=m; j++)
ret = (ret + dp(n, m, k - 1, i + 1, j)) % mod;
ret = (ret + (cm * dp(n, m, k, i + 1, cm)) % mod) % mod;
return memo[i][cm][k] = ret;
}
int numOfArrays(int n, int m, int k) {
memset(memo, -1l, sizeof memo);
long ans = 0l;
for(int i=1; i<=m; i++)
ans = (ans + dp(n, m, k-1, 1, i)) % mod;
return ans;
}
};
Time complexity : O(n * m * k)
Space complexity : O(n * m * k)
上面那種是Top down DP (應該是吧) 也是我覺得對我來說比較不會出錯的寫法
但缺點就是好像有點難對於空間再做優化
可是如果轉成bottom up填表式的話就能將Space complexity降至O(n * m)
想法大概是在填表時都是取決於上一個時間點的值 搭配上prefix sum的 就能對空間做優化
程式碼:
class Solution {
public:
int numOfArrays(int n, int m, int k) {
long mod = 1e9 + 7l;
vector<vector<long>> dp(m+1, vector<long>(k+1, 0l)), ps(m+1,
vector<long>(k+1, 0l));
for(int j=1; j<=m ;j++){
ps[j][1] = 1l * j;
dp[j][1] = 1l;
}
for(int i=2; i<=n; i++) {
auto dp2 = dp;
auto ps2 = ps;
for(int j=1; j<=m; j++) {
for(int co = 1; co <=k; co++) {
dp2[j][co] = (1l * j * dp[j][co]) % mod;
dp2[j][co] = (dp2[j][co] + ps[j - 1][co - 1]) % mod;
ps2[j][co] = (ps2[j - 1][co] + dp2[j][co]) % mod;
}
}
dp = dp2;
ps = ps2;
}
return ps[m][k];
}
};
/*
dp[i][m][k] = m * dp[i - 1][m][k] + sum(for nm in [1, m-1] dp[i - 1][nm][k -
1])
ps[m][k] = sum (for nm in [1, m] dp[nm][k])
ps[m - 1][k] = sum ( for nm in [1, m - 1] dp[nm][k - 1])
ps[m][k] - ps[m - 1][k] = dp[m][k]
*/
大概是這樣 如果有哪裡有誤 請不要感到介意讓我知道 感謝各位