【动态规划】硬币面值组合（上台阶）

逃离我推掉我的手 2022-08-09 03:16 309阅读 0赞

## 问题 ##

*  1分2分5分的硬币三种，组合成1角，共有多少种组合？
 *  有1分，2分，5分，10分四种硬币，每种硬币数量无限，给定n分钱，有多少中组合可以组成n分钱？
 *  一个人上台阶可以一次上1个，2个，或者3个，问这个人上n层的台阶，总共有几种走法？  
    问法不一样，但是本质一样！

## 解析 ##

不难发现，此题就是完全背包问题。同时也是Fibonacci的动态规划解法，所有有必要进行深入理解。  
动态规划：  
dp\[i\]\[sum\] = 用前i种硬币构成sum 的所有组合数。  
状态转移方程：  
dp\[i\]\[sum\] = dp\[i-1\]\[sum - 0\*Vm\] + dp\[i-1\]\[sum - 1\*Vm\] + dp\[i-1\]\[sum - 2\*Vm\] + … + dp\[i-1\]\[sum - K\*Vm\]; 其中K = sum / Vm

dp\[i\]\[0\] = 1 where sum= 0  
dp\[0\]\[sum\] = 0 where i=0

注意：Fibonacci解f(n-1) + f(n-2) 这种可能比较简单，但是以下这种情况就比较麻烦了：f(n-1) + f(n-2) +…+f(n-k),所以这种情况动态规划来解就比较好了。还有一点值得注意的就是，f(n-1) + f(n-2) 其实就是动态规划的状态转移方程。`dp[i] = dp[i-1] + dp[i-2]`

## 实现 ##

int coinCombinations(int coins[], int coinKinds, int sum)
    {
        vector<vector<int> > dp(coinKinds + 1, vector<int>(sum+1,0));
    
        for (int i = 0; i <= coinKinds; ++i)    //递推初始条件
        {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= coinKinds; ++i)
        {
            for (int j = 1; j <= sum; ++j)
            {
                dp[i][j] = 0;
                //j / coins[i-1]表示能取的该硬币的最大数量。
                for (int k = 0; k <= j / coins[i-1]; ++k)   //i-1是因为coins是从0开始算起的。
                {
                    dp[i][j] += dp[i-1][j - k * coins[i-1]];
                }
            }
        }
    
        return dp[coinKinds][sum];
    }

## 总结 ##

其实本题就是Fibonacci问题，对应`1分2分5分的硬币三种，组合成1角，共有多少种组合？` 这个问题就是：  
f(n) = f(n-1) + f(n-2) + f(n-5) .其中f(0) = 1 , f(1) = 1, f(2) = 2, f(3) = 2, f(4) = 3.  
后面我们还需要研究Fibonacci的解法。