动态规划之硬币组合

题目描述：现有硬币六种，分别为1元、5元、10元、20元、50元、100元，假设每种硬币数量均无限多，问用它们来凑够N元有多少种组合方式。
package ers;
import java.util.Scanner;
 /*
 * 动态规划硬币组合问题
 * 
 */
public class Main
{
    public static void main(String[] args) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext())
        {
         int n = sc.nextInt();
         int coin[] = {1,5,10,20,50,100};
         //dp[i][j]表示用前i种硬币凑成j元的组合数
         long[][] dp = new long[7][n+1]; 
         for(int i = 1; i <=n; i++)
         {
           dp[0][i]=0; //用0种硬币凑成i元的组合数为0
         }
         for(int i = 0; i <=6; i++)
         {
           dp[i][0]=1; //用i种硬币凑成0元的组合数为1,所有硬币均为0个即可
         }
         for(int i=1;i<=6;i++)
         {
             for(int j=1;j<=n;j++)
             {
                 dp[i][j] = 0;
                 for(int k =0;k<=j/coin[i-1];k++)
                 {
                     dp[i][j] += dp[i-1][j-k*coin[i-1]];
                 }      
             }
         }
         System.out.print(dp[6][n]);
      }   
    }
}