不要找错钱哦！

动态规划的基本概念实际中就是如下几个步骤：

a.分析最优解的性质，并刻画结构特征。

b.递归定义的最优解

c.以自底向上或自顶向下的方式计算出最优解

d.根据计算优值得到的信息，构造问题的最优解。

方法个数问题（动态规划解决）

有n种不同面值的货币，每种面值的货币可以使用任意张，需要找钱为aim，求换钱有多少种方法，用最少需要多少张货币能够找清。

解决方法

建立一个数组dp[n][m]，n为货币的种类数量，m为aim+1。dp[n][m]用来表示使用前n种货币兑换m面值的种数。

dp[n][m]有两种情况

• 能够使用第n种货币，dp[n][m] = dp[n-1][m]+dp[n][m-peney[n]]，dp[n-1][m]为兑换m面值使用n-1种货币时的兑换方法数量，dp[n][m-peney[n]]为兑换m-peney[n]面值使用n种货币时的兑换方法。
• 无法使用第n种货币（货币的面额比需要兑换的m值更大），此时，dp[n][m] = dp[n-1][m]，使用n种货币去兑换面值零钱的方法种数和适用n-1种货币去兑换m面值的方法一样。

#include <iostream>
using namespace std;

int ans(int n, int aim)
{
    int penny[n];
    for (int i = 0; i < n; ++i)
        cin >> penny[i];
    int dp[n][aim + 1];
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < aim + 1; ++j)
            dp[i][j] = 0;
    for (int i = 0; i < n; ++i)
        dp[i][0] = 1;
    for (int i = 1; penny[0] * i <= aim; ++i)
        dp[0][penny[0] * i] = 1;
    for (int i = 1; i < n; ++i)
        for (int j = 0; j <= aim; ++j)
        {
            if (j >= penny[i])
            {
                dp[i][j] = dp[i - 1][j] + dp[i][j - penny[i]];
            }
            else
            {
                dp[i][j] = dp[i - 1][j];
            }
        }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < aim + 1; ++j)
            cout << dp[i][j] << " ";
        cout << endl;
    }
    return dp[n - 1][aim];
}

int main()
{
    int n, aim;
    cin >> n >> aim;
    cout << ans(n, aim);
    system("pause");
    return 0;
}

最少子张问题（贪心解决）

问和上题一样的情况，用最少子张的个数是多少？

解决方法

贪心法，优先选择大面额的纸张，选到不能再选，以此类推，直至结束。

//测试事例
//{50, 20, 10, 5, 1, 0.5, 0.1}
#include <iostream>
double MONEY_UNIT[7] = {50, 20, 10, 5, 1, 0.5, 0.1}; //钱的所有面额
using namespace std;

int main()
{
    double bill_amount = 0;    //账单金额
    double actual_payment = 0; //实际付款
    double change = 0;         //找零
    cin >> bill_amount >> actual_payment;
    change = actual_payment - bill_amount;
    int sum = 0; //纸张个数
    for (int i = 0; i < 7; ++i)
    {
        if (MONEY_UNIT[i] <= change)
        {
            change -= MONEY_UNIT[i];
            i--;
            sum++;
        }
        if (!change)
            break;
    }
    cout << sum << endl;
    system("pause");
    return 0;
}