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]
*/
大概是这样 如果有哪里有误 请不要感到介意让我知道 感谢各位