HDU 2069 Coin Change

题目链接~~>

做题感悟：开始在UVA上做了一个和这个类似的，只不过没有 100 个硬币的限制，加上这个限制就不知道如何是好！！！

解题思路：多了一个条件，只需要多加一维就可以，dp[ i ] [ j ] +=dp [ i-1][ j - w] ;  i 代表有几枚硬币，j代表价值。

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<string>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<math.h>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      const int INF = -999999 ;
     
    
   

    

     

    
    

     

      const int MX= 50005 ;
     
    
   

    

     

    
    

     

      int dp[105][MX] ;
     
    
   

    

     

    
    

     

      int w[10]={1,5,10,25,50} ;
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 memset(dp,0,sizeof(dp)) ;
     
    
   

    

     

    
    

     

       dp[0][0]=1 ;
     
    
   

    

     

    
    

     
 for(int i=0 ;i<5 ;i++)
     
    
   

    

     

    
    

     
 for(int j=1 ;j<=100 ;j++)
     
    
   

    

     

    
    

     
 for(int k=w[i] ;k<=250 ;k++)
     
    
   

    

     

    
    

     

       dp[j][k]+=dp[j-1][k-w[i]] ;
     
    
   

    

     

    
    

     
 int sum=0,n ;
     
    
   

    

     

    
    

     
 while(~scanf("%d",&n))
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       sum=0 ;
     
    
   

    

     

    
    

     
 for(int i=0 ;i<=100 ;i++)
     
    
   

    

     

    
    

     

       sum+=dp[i][n] ;
     
    
   

    

     

    
    

     
 printf("%d\n",sum) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/20647435