1023. 买书

题目描述

书有4种，每种价格不同，每本书可以无限买，问刚好花m块钱的方案数？

基本分析

1. 完全背包裸题

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAX_M = 1000;
int f[MAX_M + 10];
int v[5] = {0, 10, 20, 50, 100};

int m;

int main()
{
    scanf("%d", &m);
    
    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\n", f[m]);
    
    return 0;
}

总结

1. 朴素定义？f[i][j]表示买前i本书，价格恰好为j的方案数
2. 空间优化？第二维度正序遍历