SMMR-T106: Boost Up

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1e9 + 7;

vector<int> ninja;
int nf, target;

int KnapsackNinja(int n, int p){
    if(p == 0){
        return 1;
    } else if(n == 0 && p != 0){
        return 0;
    } else {
        int choose = (p >= ninja[n])? KnapsackNinja(n, p - ninja[n]) : 0;
        int notchoose = KnapsackNinja(n - 1, p);
        return (choose + notchoose) % MOD;
    }
}

int main(){

    scanf("%d %d", &nf, &target);
    ninja.assign(nf + 1, 0);
    for(int i = 1; i <= nf; ++i){
        scanf("%d", &ninja[i]);
    }

    vector<vector<int>> memo(nf + 1, vector<int>(target + 1, 0));
    for(int n = 0; n <= nf; ++n){
        for(int p = 0; p <= target; ++p){
            if(p == 0){
                memo[n][p] = 1;
            } else if(n == 0){
                continue;
            } else {
                int choose = (ninja[n] > p)? 0 : memo[n][p - ninja[n]];
                int notchoose = memo[n - 1][p];
                memo[n][p] = (choose + notchoose) % MOD;
            }
        }
    }

    cout << memo[nf][target];

    return 0;
}