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];
}
};

大师 我直接递回 超烂