AcWing 1023. 买书

题目传送门

一、二维原始解法

#include 

using namespace std;
const int N = 1010;
int v[5] = {0, 10, 20, 50, 100};
int f[5][N];

int main() {
    int m;
    cin >> m;
    //base case
    f[0][0] = 1;
    for (int i = 1; i <= 4; i++)
        for (int j = 0; j <= m; j++) {
            //可以第i个物品选择0个，所以f[i][j]=f[i-1][j]
            f[i][j] = f[i - 1][j];
            //类似于前缀和的思想，利用前面的最优化方案数，
            //再考虑增多空间情况下的数量,不断的递增过来，就是最多的方案数
            if (v[i] <= j)f[i][j] += f[i][j - v[i]];
        }
    //一个整数，代表选择方案种数
    printf("%d", f[4][m]);
    return 0;
}

二、一维终极解法

#include 

using namespace std;
const int N = 1010;
int v[5] = {0, 10, 20, 50, 100};
int f[N];

int main() {
    int m;
    cin >> m;
    //base case
    f[0] = 1;
    for (int i = 1; i <= 4; i++)
        for (int j = v[i]; j <= m; j++)
            f[j] += f[j - v[i]];
    //一个整数，代表选择方案种数
    printf("%d", f[m]);
    return 0;
}