推 oin1104: 大師 我直接遞迴 超爛 08/13 01:41
→ sixB: 你比我厲害多了 我弟會寫不好：（ 08/14 01:41
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];
}
};
-----
Sent from JPTT on my iPad
--
很姆的咪
姆之咪
http://i.imgur.com/5sw7QOj.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.135.99.218 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1755016206.A.8CE.html