题目描述

题目重述：总和为m，分成n个数（可以是0），不考虑顺序，求分的方法总数

(简单dp) $O(n*m)$

数据结构：dp[i][j]表示总和为i，分成了j个数
求dp[i][j]分成二种情况：
第一种：最小值为0，那么就等于dp[i][j-1]（删去0那个数，总和为i，分成了j-1个数）
第二种：最小值不为0，把每个数减去1，即等于dp[i-j][j] ，(总和为i-j，分成j个数)
二者之和即为dp[i][j]
如何判断是否存在第二种情况（第一种情况一定存在）：i>=j,总和大于等于总数

C++ 代码

#include <iostream>  
#include <algorithm>  
#include <cstdio> 
#include <string> 
using namespace std;
const int N = 120;
int dp[N][N];    //dp[i][j]总和是i分成j个数的方案的和
int main()
{
    int n, k, m;
    int t;
    cin >> t;
    while (t--) {
        scanf("%d%d", &m, &n);
        dp[0][0] = 1;  //总和是0，分成0个数的方案数目为1，
        for (int i = 0; i <= m; i++)  //总和从0到m
            for (int j = 1; j <= n; j++)  //个数从1到n
            {
                dp[i][j] = dp[i][j - 1];  //第一种情况，最小值为0，所以加上dp[i][j-1] (j-1个数总和为i)
                if (i >= j) dp[i][j] += dp[i - j][j]; //第二种情况，最小值不为0，但凡总和大于等于个数，就存在第二种情况
                //这里发现，如果i==j，那么第二种情况下为1,1,1,1,1,1……所以减去1后，为0,0,0，0,0……，所以dp[0][0] = 1;
            }
        printf("%d\n", dp[m][n]); //总和是m分成n个数的方案的和
    }
    return 0;
}