本文共 892 字，大约阅读时间需要 2 分钟。

    有数组penny，penny中所有的值都为正数且不重复。

    每个值代表一种面值的货币，每种面值的货币可以使用任意张。

    再给定一个整数aim(小于等于1000)代表要找的钱数，求换钱有多少种方法。

    给定数组penny及它的大小(小于等于50)，同时给定一个整数aim，请返回有多少种方法可以凑成aim。

class Exchange {public:    int countWays(vector
   
     penny, int n, int aim)     {        vector
    
     
       >dp(n,vector
      
       (aim+1, 0));//用0-n种货币组成aim钱的矩阵        //状态转移方程 dp[i][j] = dp[i-1][j]+dp[i][j-penny[i]];        for (int i=1; i<=aim; ++i)            if(i%penny[0]==0)                dp[0][i] = 1;        for (int i=1; i
       
        =penny[i])                    dp[i][j] = dp[i-1][j]+dp[i][j-penny[i]];                else                    dp[i][j] = dp[i-1][j];        }        return dp[n-1][aim];    }};
       
      
     
    
   

化简后

class Exchange {public:    int countWays(vector
   
     penny, int n, int aim)     {        vector
    
     dp(aim+1,0);//存在凑成0-aim种钱数的方法.        dp[0] = 1;        for(int i=0;i
    
   

转载地址：http://uehji.baihongyu.com/