f*****u
发帖数: 308 | 1 网上看到下面的解法，代码看上去非常简洁漂亮。看了半天还是没看明白getWays里面
两个for循环怎么就算出所有的解法种数的。哪个大牛能给解释一下，非常感谢！
问题概述：m是基，对于给定数n，求n == x0*m^0 + x1*m^1 + x2*m^2 + ...的所有解
（x0, x1, x2, ...）的总个数。
#define MOD 1000000007
int getWays(int n, int m) {
vector w = vector(n + 1, 0);
for (long long i = 1; i <= n; i *= m) {
w[i] = (w[i] + 1) % MOD;
for (int j = i + 1; j <= n; j++) {
w[j] = (w[j] + w[j - i]) % MOD;
}
}
return w[n];
} |
f*****u
发帖数: 308 | |
p*****2
发帖数: 21240 | |
f*****u
发帖数: 308 | 4 weekly contest.
【在 p*****2 的大作中提到】
: 哪个category的？
|
p*****2
发帖数: 21240 | 5
这个weekly contest做了之后有什么用呢？
【在 f*****u 的大作中提到】
: weekly contest.
|
f*****u
发帖数: 308 | 6 二爷有所不知，这不是昨天Leetcode挂了，我就上hackerrank想做一题，结果卡这儿了
，不搞明白挺难受的。关键是觉得这个解法还是挺有意思的。
【在 p*****2 的大作中提到】
:
: 这个weekly contest做了之后有什么用呢？
|
p*****2
发帖数: 21240 | 7
回头我也看看。
【在 f*****u 的大作中提到】
: 二爷有所不知，这不是昨天Leetcode挂了，我就上hackerrank想做一题，结果卡这儿了
: ，不搞明白挺难受的。关键是觉得这个解法还是挺有意思的。
|
f*****u
发帖数: 308 | 8 好，等着二爷好消息。
【在 p*****2 的大作中提到】
:
: 回头我也看看。
|
d*******3
发帖数: 58 | 9 这个就是经典的换钱问题啊,用dp做,这题里限制就是零钱必须是 m^d.
假设 s[1...m] 是零钱值，n是要换的值，dp[i][j]表示当前值为i，可选零钱为s[1..j
]是的环法数，
dp[i][j] = dp[i][j-1] + dp[i-s[j][j],
这个空间是O(n*m),可以优化成O(n)的，就是你贴那个代码里的 |
p*****2
发帖数: 21240 | 10
这题不错。典型DP。大家都应该做做。面G，F碰到很正常。
【在 f*****u 的大作中提到】
: 好，等着二爷好消息。
|
|
|
p*****2
发帖数: 21240 | 11
这个代码写的很好。
【在 f*****u 的大作中提到】
: 网上看到下面的解法，代码看上去非常简洁漂亮。看了半天还是没看明白getWays里面
: 两个for循环怎么就算出所有的解法种数的。哪个大牛能给解释一下，非常感谢！
: 问题概述：m是基，对于给定数n，求n == x0*m^0 + x1*m^1 + x2*m^2 + ...的所有解
: （x0, x1, x2, ...）的总个数。
: #define MOD 1000000007
: int getWays(int n, int m) {
: vector w = vector(n + 1, 0);
: for (long long i = 1; i <= n; i *= m) {
: w[i] = (w[i] + 1) % MOD;
: for (int j = i + 1; j <= n; j++) {
|
m****1
发帖数: 41 | 12 对呀~~ 我也是写完才发现可以用 1D array~~ 得总结下这种题~
【在 p*****2 的大作中提到】
:
: 这个代码写的很好。
|
p*****2
发帖数: 21240 | 13
这句也很精妙
for (long long i = 1; i <= n; i *= m)
我还不知道scala怎么写呢？
【在 m****1 的大作中提到】
: 对呀~~ 我也是写完才发现可以用 1D array~~ 得总结下这种题~
|
m****1
发帖数: 41 | 14 不懂scala... 或者scala可以做个pow(m,k)function, k++ 的loop么？ |
f*****u
发帖数: 308 | 15 很受教，谢谢！
.j
【在 d*******3 的大作中提到】
: 这个就是经典的换钱问题啊,用dp做,这题里限制就是零钱必须是 m^d.
: 假设 s[1...m] 是零钱值，n是要换的值，dp[i][j]表示当前值为i，可选零钱为s[1..j
: ]是的环法数，
: dp[i][j] = dp[i][j-1] + dp[i-s[j][j],
: 这个空间是O(n*m),可以优化成O(n)的，就是你贴那个代码里的
|
f*****u
发帖数: 308 | 16 二爷能总结一下这个题不？
【在 p*****2 的大作中提到】
:
: 这句也很精妙
: for (long long i = 1; i <= n; i *= m)
: 我还不知道scala怎么写呢？
|
f*****u
发帖数: 308 | 17 对于这个典型的背包问题，找到一个非常好的教程，有兴趣的可以去看看。GitHub链接
在这儿：https://github.com/tianyicui/pack
【在 f*****u 的大作中提到】
: 网上看到下面的解法，代码看上去非常简洁漂亮。看了半天还是没看明白getWays里面
: 两个for循环怎么就算出所有的解法种数的。哪个大牛能给解释一下，非常感谢！
: 问题概述：m是基，对于给定数n，求n == x0*m^0 + x1*m^1 + x2*m^2 + ...的所有解
: （x0, x1, x2, ...）的总个数。
: #define MOD 1000000007
: int getWays(int n, int m) {
: vector w = vector(n + 1, 0);
: for (long long i = 1; i <= n; i *= m) {
: w[i] = (w[i] + 1) % MOD;
: for (int j = i + 1; j <= n; j++) {
|
