3181 -- Dollar Dayz
public static void main(String[] args) { Scanner in = new Scanner(System.in); int N = in.nextInt(); int K = in.nextInt(); System.out.println(solve(N, K)); in.close(); } public static BigInteger solve(int N, int K){ BigInteger[][] dp = new BigInteger[K + 1][N + 1]; for (int i = 0; i < dp.length; i++){ for (int j = 0; j < dp[0].length; j++){ dp[i][j] = BigInteger.ZERO; } } dp[0][0] = BigInteger.ONE; for (int i = 1; i <= K; ++i) { for (int k = 0; k <= N; k += i) { for (int j = N; j >= k; --j) { dp[i][j] = dp[i][j].add(dp[i - 1][j - k]); } } } return dp[K][N]; }
public static BigInteger solve(int N, int K){ BigInteger[][] dp = new BigInteger[K + 1][N + 1]; for (int i = 0; i < dp.length; i++){ for (int j = 0; j < dp[0].length; j++){ dp[i][j] = BigInteger.ZERO; } } dp[0][0] = BigInteger.ONE; for (int i = 1; i <= K; ++i) { //必须得初始化,dp[i][0]不能由dp[0][0]推得 dp[i][0] = BigInteger.ONE; for (int j = 1; j <= N; ++j){ if (j < i){ dp[i][j] = dp[i-1][j]; } else{ dp[i][j] = dp[i-1][j].add(dp[i][j-i]); } } } return dp[K][N]; }
https://shanzi.gitbooks.io/algorithm-notes/content/problem_solutions/dollar_daz.html
完全背包+简单高精度加法
http://www.cnblogs.com/kuangbin/archive/2012/09/20/2695165.html
Farmer John goes to Dollar Days at The Cow Store and discovers an unlimited number of tools on sale. During his first visit, the tools are selling variously for $1, $2, and $3. Farmer John has exactly $5 to spend. He can buy 5 tools at $1 each or 1 tool at $3 and an additional 1 tool at $2. Of course, there are other combinations for a total of 5 different ways FJ can spend all his money on tools. Here they are:
1 @ US$3 + 1 @ US$2 1 @ US$3 + 2 @ US$1 1 @ US$2 + 3 @ US$1 2 @ US$2 + 1 @ US$1 5 @ US$1Write a program than will compute the number of ways FJ can spend N dollars (1 <= N <= 1000) at The Cow Store for tools on sale with a cost of $1..$K (1 <= K <= 100).
Input
A single line with two space-separated integers: N and K.
http://blog.csdn.net/u014688145/article/details/71136194dp[i][j] :用i种价格配出金额j的方案数 初始化: dp[i][0] = 1; 用i中价格配出金额0的方案数为1 递推式: dp[i][j] = dp[i-1][j] + dp[i-1][j-i] + dp[i-1][j-2*i] + ... + dp[i-1][0] 如: 1 * x + 2 * y = 5; y = 0, 1 * x = 5 y = 1, 1 * x = 3 y = 2, 1 * x = 1 dp[2][5] = dp[1][5] + dp[1][3] + dp[1][1]农夫约翰有N元钱,市场上有价值1……K的商品无限个,求所有的花钱方案?
public static void main(String[] args) { Scanner in = new Scanner(System.in); int N = in.nextInt(); int K = in.nextInt(); System.out.println(solve(N, K)); in.close(); } public static BigInteger solve(int N, int K){ BigInteger[][] dp = new BigInteger[K + 1][N + 1]; for (int i = 0; i < dp.length; i++){ for (int j = 0; j < dp[0].length; j++){ dp[i][j] = BigInteger.ZERO; } } dp[0][0] = BigInteger.ONE; for (int i = 1; i <= K; ++i) { for (int k = 0; k <= N; k += i) { for (int j = N; j >= k; --j) { dp[i][j] = dp[i][j].add(dp[i - 1][j - k]); } } } return dp[K][N]; }
递推式优化:
dp[i][j] = dp[i-1][j] + dp[i-1][j-i] + dp[i-1][j-2*i] + ... + dp[i-1][0];
dp[i][j-i] = dp[i-1][j-i] + dp[i-1][j-2*i] + dp[i-1][j-3*i] + ... + dp[i-1][0];
所以有:
dp[i][j] = dp[i-1][j] + dp[i][j-i];public static BigInteger solve(int N, int K){ BigInteger[][] dp = new BigInteger[K + 1][N + 1]; for (int i = 0; i < dp.length; i++){ for (int j = 0; j < dp[0].length; j++){ dp[i][j] = BigInteger.ZERO; } } dp[0][0] = BigInteger.ONE; for (int i = 1; i <= K; ++i) { //必须得初始化,dp[i][0]不能由dp[0][0]推得 dp[i][0] = BigInteger.ONE; for (int j = 1; j <= N; ++j){ if (j < i){ dp[i][j] = dp[i-1][j]; } else{ dp[i][j] = dp[i-1][j].add(dp[i][j-i]); } } } return dp[K][N]; }
https://shanzi.gitbooks.io/algorithm-notes/content/problem_solutions/dollar_daz.html
完全背包+简单高精度加法
http://www.cnblogs.com/kuangbin/archive/2012/09/20/2695165.html
看上面这个式子a[i][j]=a[i][j-1]+a[i-j][j-1]+a[i-2j][j-1]+a[i-3j][j-1]…+a[0][j-1]我们可以发现,其实可以转到a[i][j]的状态有两种,一种是a[i][j-1]就是不用j这个数字拼接i这个数字的方法数,另一种是a[i-j][j]就是用了j这个数字拼接的到i-j的方法数那么状态转移方程就可以写成a[i][j]=a[i][j-1]+a[i-j][j]不用加那么多项,就降低了一个数量级的复杂度
http://www.hankcs.com/program/cpp/poj-3181-dollar-dayz.html
http://d.hatena.ne.jp/komiyam/20121026/1351261358
http://blog.csdn.net/kenden23/article/details/41695331
//大整数类
class BigNum
{
public:
BigNum(){}
BigNum(long long high,long long low):high(high),low(low){}
long long high; //高18位
long long low; //低18位
//相加运算
BigNum operator+(BigNum &B)
{
long long high_tmp = (low+B.low)/BASE+high+B.high;
long long low_tmp = (low+B.low)%BASE;
return BigNum(high_tmp, low_tmp);
}
//输出值
void print()
{
if(!high)//高位为0
printf("%I64d\n",low);
else //高位非0
{
printf("%I64d",high);
printf("%018I64d",low);
}
}
}dp[maxn];
int main()
{
while(scanf("%d%d",&n,&k)==2)
{
//初始化
memset(dp,0,sizeof(dp));
dp[0].low=1;//等效于令dp[0]=0;
//递推
for(int i=1;i<=k;i++)
{
for(int j=i;j<=n;j++)
dp[j] = dp[j]+dp[j-i];
}
//输出
dp[n].print();
}
return 0;
}
Read full article from 3181 -- Dollar Dayz
http://www.hankcs.com/program/cpp/poj-3181-dollar-dayz.html
dp[i][j] := 用i种价格配出金额j的方案数。
那么dp[i][0] = 1,使用任何价格配出金额0的方案个数都是1(什么都不用)。
递推关系式:
dp[i][j] = dp[i – 1][j] + dp[i – 1][j – i] + dp[i – 1][j – 2 * i] + … + dp[i – 1][0]
cin >> N >> K;
dp[0][0] = 1;
for
(
int
i = 1; i <= K; ++i)
{
for
(
int
k = 0; k <= N; k += i)
{
for
(
int
j = N; j >= k; --j)
{
dp[i][j] += dp[i - 1][j - k];
}
}
}
cout << dp[K][N] << endl;
for
(
int
i = 1; i <= K; ++i)
{
dp[i][0][1] = 1;
for
(
int
j = 1; j <= N; ++j)
{
if
(j < i)
{
dp[i][j][0] = dp[i - 1][j][0];
dp[i][j][1] = dp[i - 1][j][1];
}
else
{
dp[i][j][0] = dp[i - 1][j][0] + dp[i][j - i][0];
dp[i][j][1] = dp[i - 1][j][1] + dp[i][j - i][1];
// 高位进位
dp[i][j][0] += dp[i][j][1] / LIMIT_ULL;
// 低位限制
dp[i][j][1] = dp[i][j][1] % LIMIT_ULL;
}
}
}
if
(dp[K][N][0])
{
cout << dp[K][N][0];
}
cout << dp[K][N][1] << endl;
http://blog.csdn.net/kenden23/article/details/41695331
- void getCombinations(int N, int K)
- {
- memset(hiBit, 0, sizeof(long long) * (N+1));
- memset(lowBit, 0, sizeof(long long) * (N+1));
- lowBit[0] = 1LL;
- for (int i = 1; i <= K; i++)
- {
- for (int j = i; j <= N; j++)
- {
- lowBit[j] += lowBit[j-i];//买和不买i物品的和,就是当前组合和了
- hiBit[j] += lowBit[j] / MOD + hiBit[j-i];//错误:忘记hiBit[j-i]
- lowBit[j] %= MOD;//保存低位
- }
- }
- }
//大整数类
class BigNum
{
public:
BigNum(){}
BigNum(long long high,long long low):high(high),low(low){}
long long high; //高18位
long long low; //低18位
//相加运算
BigNum operator+(BigNum &B)
{
long long high_tmp = (low+B.low)/BASE+high+B.high;
long long low_tmp = (low+B.low)%BASE;
return BigNum(high_tmp, low_tmp);
}
//输出值
void print()
{
if(!high)//高位为0
printf("%I64d\n",low);
else //高位非0
{
printf("%I64d",high);
printf("%018I64d",low);
}
}
}dp[maxn];
int main()
{
while(scanf("%d%d",&n,&k)==2)
{
//初始化
memset(dp,0,sizeof(dp));
dp[0].low=1;//等效于令dp[0]=0;
//递推
for(int i=1;i<=k;i++)
{
for(int j=i;j<=n;j++)
dp[j] = dp[j]+dp[j-i];
}
//输出
dp[n].print();
}
return 0;
}
Read full article from 3181 -- Dollar Dayz