硬币找零问题之动态规划(3)

给定一个有n个正整数的数组A和一个整数sum,求选择数组A中部分数字和为sum的方案数。当两种选取方案有一���数字的下标不一样,我们就认为是不同的组成方案。

输入描述:  输入为两行: 第一行为两个正整数n(1 ≤ n ≤ 1000)，sum(1 ≤ sum ≤ 1000)，第二行为n个正整数A[i](32位整数)，以空格隔开。

输出描述:  输出所求的方案数

输入例子:

5 15

5 5 10 2 3

输出例子:

4

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;

int main(){
    long long a, sum;
    while (cin >> a >> sum){
        vector<int> vec(a);
        for (int i = 0; i<a; i++)  cin >> vec[i];

vector<vector<long>> dp(a, vector<long>(sum + 1, 0));
        for (int i = 0; i < a; i++){
            dp[i][0] = 1;
        }

if (sum >= vec[0]){
            dp[0][vec[0]] = 1;
        }

for (int i = 1; i<a; i++){
            for (int j = 1; j <= sum; j++){
                if (j >= vec[i]){
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - vec[i]];
                }
                else
                {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        cout << dp[a - 1][sum] << endl;
    }
}                                   

进一步的优化交给读者自己思考咯。