2787.
數數兒dp我要死了啊啊啊啊啊啊
原本想說洗完澡趕快寫一寫要睡了
從後面跑遞迴感覺可以省很多步
然後我就一直寫錯改很多次
最後認命從前面慢慢疊==
我就這樣了
using ll = long long;
class Solution {
public:
int numberOfWays(int n, int x) {
ll mod = 1e9 + 7;
vector<int> pool;
for(int i = 1; pow(i, x) <= n; i++){
pool.push_back(pow(i, x));
}
int res = 0;
vector<int> dp(n+1, 0);
dp[0] = 1;
for(int i: pool){
vector<int> next = dp;
for(int j = 0; (j + i) <= n; j++){
if(dp[j] != 0) next[j+i] += dp[j];
next[j+i] %= mod;
}
dp = move(next);
}
return dp[n];
}
};

大師 我直接遞迴 超爛