Square Coins一个DP问题分析

问题描述：

People in Silverland use square coins. Not only they have square shapes but also their values are square numbers. Coins with values of all square numbers up to 289 (=17²), i.e., 1-credit coins, 4-credit coins, 9-credit coins, ..., and 289-credit coins, are available in Silverland.

There are four combinations of coins to pay ten credits:

ten 1-credit coins,
one 4-credit coin and six 1-credit coins,
two 4-credit coins and two 1-credit coins, and
one 9-credit coin and one 1-credit coin.

Your mission is to count the number of ways to pay a given amount using coins of Silverland.

Input

The input consists of lines each containing an integer meaning an amount to be paid, followed by a line containing a zero. You may assume that all the amounts are positive and less than 300.

Output

For each of the given amount, one line containing a single integer representing the number of combinations of coins should be output. No other characters should appear in the output.

Sample Input

2
10
30
0

Sample Output

1
4
27

问题分析：

这个问题是个典型的动态规划问题，从底往上推就行了。
这个问题的关键是建立递推式：
二维数组w，其中w[i][j]代表使用<=i*i的币值的钱币来付款j元钱的的可能的方法数
这样我们对w[i][j]来构造递推式：
w[i][j] = sum { w[i-1][j-k*i*i] } 其中k=0,1,... j-k*i*i >= 0
这个个含义是使用<=i*i的币值的钱币付j元钱的方法数，就是我用0...k个i*i币值来
替换掉以前用<=(i-1)*(i-1)币值的等额的钱 来付j元钱的方法数。而用i*i替换出等
额钱的方法数，其实就是用<=(i-1)*(i-1)币值的钱来付j-k*i*i的方法数。
理解这个公式也就很容易理解代码了。

cpp 代码

#include<iostream></iostream>
using namespace std;

int w[18][301];

void NumOfMethod(){
     int i,j,k;
    /*初始化w的值，用<=1币值显然有一种方法，j=0初始化为1的原因是，
      w[i][j] += w[i-1][j-k*i*i]，如果j-k*i*i == 0,即用k个币值为
      i*i的硬币恰好可以替换所有的所有的硬币来支付，这个方法数是1而不是0，
      这比较特殊，与用<=(i-1)*(i-1)币值的钱来付j-k*i*i的方法数不相等*/

    for(i = 1; i < 18; i++)
        for(j = 0; j < 301; j++){
           if(i == 1 || j == 0)
               w[i][j] = 1;
           else
               w[i][j] = 0;
        }
    //下面就是从底往上推的一个过程了:
    for(i = 2; i < 18; i++)
        for(j = 1; j < 301; j++)
            for(k = 0; j-k*i*i >= 0; k++)
                w[i][j] += w[i-1][j-k*i*i];

}
int main(){
    int n;
    NumOfMethod();
    while(cin>>n,n){
      cout << w[17][n] << endl;
    }
    return 0;
}

 

     当然如果想节省空间可以用两个一维的数组交替使用来替换掉w那个二维数组。

分享到：

Function Run Fun一个简单的DP问题分析 | [转]MAP/REDUCE:Google和Nutch实现异同及 ...

• 2007-12-16 22:32
• 浏览 2656
• 评论(1)
• 查看更多

评论

1 楼 fuliang 2007-12-17  

初始化w的值，用<=1币值显然有一种方法，j=0初始化为1的原因是，w[i][j] += w[i-1][j-k*i*i]，如果j-k*i*i == 0,即用k个币值为i*i的硬币恰好可以替换所有的所有的硬币来支付，这个方法数是1而不是0，这比较特殊，与用<=(i-1)*(i-1)币值的钱来付j-k*i*i的方法数不相等(当然也可以认为支付0元的方法为1)