笔记——零钱兑换

方法一：暴力解法（遍历）：

int main()
{
    int n, count = 0;

    cin >> n;
    for(int i = 0; i <= n/5; i++)
    {
        for(int j = 0; j <= n/2; j++)
        {
            if((i*5 + j*2) > n)
            {
                break;
            }
            for(int k = 0; k <= n; k++)
            {
                if((i*5 + j*2 + k) > n)
                {
                    break;
                }
                else if((i*5 + j*2 + k) == n)
                {
                    count++;
                }
            }
        }
    }
    cout << count << endl;

    return 0;
}

方法二：只需考虑5元和2元，只要不超过n，剩下的全换1元即是1种方法

int main()
{
    int n, count = 0;

    cin >> n;
    for(int i = 0; i <= n/5; i++)
    {
        for(int j = 0; j <= n/2; j++)
        {
            if((i*5 + j*2) > n)
            {
                break;
            }
            else
            {
                count++;
            }
        }
    }
    cout << count << endl;

    return 0;
}

方法三：先取出i张5元，剩下的钱只用2元和1元。则剩下的钱，只用1元为1种方法，能换1张2元则多一种方法，即剩下的钱/2+1种方法

int main()
{
    int n, count = 0;

    cin >> n;
    for(int i = 0; i <= n/5; i++)
    {
        count += (n - 5*i)/2 + 1;
    }
    cout << count << endl;

    return 0;
}