2019拼多多学霸批第二批笔试题第三题C++解法及解析。

参考：2019 拼多多校招第三题sum 服务端研发工程师

题目描述

给定两个正整数N和S，你需要找出所有的长度为N的正整数数列中，满足单调递增以及总和为S的数列有多少个。

输入描述

共一行，两个整数N和S（1 < N, S < 1000）。

输出描述

一个整数，为满足条件的数列个数对100000007取模的结果。

分析

  • 最佳解法：动态规划，这里用vec[n][s]表示和为s长度为n的序列个数。
  • 状态转换方程：vec[n][s] = vec[n][s-n] + vec[n-1][s-n]
  • 解释：
    • vec[n][s-n]：表示和为s-n的长度为n的序列个数（把它们都加上1，便成了开头数字为非1且和为s的长度为n的序列个数）；
    • vec[n-1][s-n]：表示开头数字为非1，和为s-n的长度为n-1的序列个数（把它们都加上1，然后在序列开头加入1，便成了开头数字为1且和为s的长度为b的序列个数）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void getCnt(const int& N, const int& S, vector<vector<int> >& vec) {
    if (vec[N][S] != 0)
        return;
        
    for (int i = 2; i <= N; ++i) {
        for (int j = i + 1; j <= S; ++j)
            vec[i][j] = (vec[i][j-i] + vec[i-1][j-i]) % 1000000007;
    }
}

int main() {
    int N, S;
    
    while(cin >> N >> S) {
        vector<vector<int> > vec(N + 1, vector<int>(S + 1, 0));
        for (int i = 1; i <= S; ++i)
            vec[1][i] = 1;
    
        getCnt(N, S, vec);
        cout << vec[N][S] % 1000000007 << endl;
    }
    return 0;
}