天天看点

【动态规划】硬币面值组合(上台阶)

问题

  • 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 + , vector<int>(sum+,));

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

    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的解法。

继续阅读