[acwing]1023.小明买书

/*
	dp[i][j] 表示只考虑前 i 个物品，其价值恰好为 j 的方案个数
	
	dp[i][j] 可从选多少个第 i 个物品推导出来，假设最多能选 s 个
	如果选 0 个第 i 个物品，dp[i][j] = dp[i - 1][j - vi * 0]
	如果选 1 个第 i 个物品，dp[i][j] = dp[i - 1][j - vi * 1]
	......
	如果选 s 个第 i 个物品，dp[i][j] = dp[i - 1][j - vi * s]
	综上，
	dp[i][j] = dp[i - 1][j - vi * 0] + dp[i - 1][j - vi * 1] + ... + dp[i - 1][j - vi * s]
	那么，
	dp[i][j - vi] = dp[i - 1][j - vi * 1] + dp[i - 1][j - vi * 2] + ... + dp[i - 1][j - vi * s]
	即，
	dp[i][j] = dp[i - 1][j] + dp[i][j - vi]
	
	遍历顺序应该是从上到下 i[1, 4]，从左到右的 j[0, n]
	
	初始化 dp[0][0] = 1
	
	目标 dp[4][n]
*/
#include <cstdio>

using namespace std;

const int N = 1010;

int n;
int v[] = {-1, 10, 20, 50, 100};
int dp[5][N];

int main()
{
    scanf("%d", &n);
    
    dp[0][0] = 1;
    
    for (int i = 1; i <= 4; i++)
        for (int j = 0; j <= n; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= v[i]) dp[i][j] += dp[i][j - v[i]];
        }
        
    printf("%d", dp[4][n]);        
    
    return 0;
}

/*
	空间优化
*/
#include <cstdio>

using namespace std;

const int N = 1010;

int n;
int v[] = {-1, 10, 20, 50, 100};
int dp[N];

int main()
{
    scanf("%d", &n);
    
    dp[0] = 1;
    
    for (int i = 1; i <= 4; i++)
        for (int j = 0; j <= n; j++) {
            if (j >= v[i]) dp[j] += dp[j - v[i]];
        }
        
    printf("%d", dp[n]);        
    
    return 0;
}

[acwing]1050.鸣人的影分身

/*
	dp[i][j][k] 表示只考虑前 i 个物品，其价值恰好为 j，且所选物品个数为 k 的方案的数量
	
	dp[i][j][k] 可从选多少个第 i 个物品推导出来，假设最多能选 s 个
	如果选 0 个第 i 个物品，dp[i][j][k] = dp[i - 1][j - vi * 0][k - 0]
	如果选 1 个第 i 个物品，dp[i][j][k] = dp[i - 1][j - vi * 1][k - 1]
	......
	如果选 s 个第 i 个物品，dp[i][j][k] = dp[i - 1][j - vi * s][k - s]
	综上，
	dp[i][j][k] = dp[i - 1][j - vi * 0][k - 0] + dp[i - 1][j - vi * 1][k - 1] + ... + dp[i - 1][j - vi * s][k - s]
	那么，
	dp[i][j - vi][k - 1] = dp[i - 1][j - vi * 1][k - 1] + dp[i - 1][j - vi * 2][k - 2] + ... + dp[i - 1][j - vi * s][k - s]
	即，
	dp[i][j][k] = dp[i - 1][j][k] + dp[i][j - vi][k - 1];
	
	遍历顺序应该是 i[1, m + 1]，j[0, m]，k[0, n]
	
	初始化 dp[0][0][0] = 1
	
	目标 dp[m + 1][m][n]
*/
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 20;

int t, m, n;
int dp[N][N][N];

int main()
{
    scanf("%d", &t);
    while (t--) {
        memset(dp, 0, sizeof(dp));
        scanf("%d%d", &m, &n);
        
        dp[0][0][0] = 1;
        
        for (int i = 1; i <= m + 1; i++)
            for (int j = 0; j <= m; j++)
                for (int k = 0; k <= n; k++) {
                    int vi = i - 1;
                    dp[i][j][k] = dp[i - 1][j][k];
                    if (j - vi >= 0 && k - 1 >= 0) dp[i][j][k] += dp[i][j - vi][k - 1];
                }
                
        printf("%d\n", dp[m + 1][m][n]);
    }
    
    return 0;
}

/*
	空间优化
*/
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 20;

int t, m, n;
int dp[N][N];

int main()
{
    scanf("%d", &t);
    while (t--) {
        memset(dp, 0, sizeof(dp));
        scanf("%d%d", &m, &n);
        
        dp[0][0] = 1;
        
        for (int i = 1; i <= m + 1; i++)
            for (int j = 0; j <= m; j++)
                for (int k = 0; k <= n; k++) {
                    int vi = i - 1;
                    if (j - vi >= 0 && k - 1 >= 0) dp[j][k] += dp[j - vi][k - 1];
                }
                
        printf("%d\n", dp[m][n]);
    }
    
    return 0;
}