题解 | #零钱兑换#

题目描述 n元人民币换成1元、2元、5元的零钱，请计算共有多少种兑换方法？
解法一：暴力破解

using namespace std;
int main(){
    int n,count = 0;
    cin>>n;
    for(int i = 0;i <= n;i++)
        for(int j = 0;j <= n; j+=2)
            for(int k = 0;k <= n; k+=5)
                if(i+j+k == n)
                    count++;
    cout<<count;
}

解法二：只算5元和2元的，剩下的一元来凑，只要多张5元和2元加起来不超过总数就算一次

#include<iostream>
using namespace std;
int main(){
    int n,count = 0;
    cin>>n;
    for(int j = 0; j <= n; j+=5)
        for(int k = 0; k <= n; k+=2)
            if(j+k > n)
                break;
            else
                count++;
    cout<<count;
}

解法三：只算5元的，剩下的钱，1元的一种，每可以多兑换2元就会多一种 --> 即：剩下的钱/2种
再加上一元的一种，结果就是：剩下的钱/2+1。遍历5元的即可。

using namespace std;
int main(){
    int n,count = 0;
    cin>>n;
    for(int j = 0; j <= n; j+=5)
        count+=(n-j)/2+1;
    cout<<count;
}