Untitled

 avatar
unknown
c_cpp
2 years ago
914 B
8
Indexable
int mod=1e9+7;
int find(int i,int target,int cap,int n,vector<vector<int>>& dp){
    if(i>n){
        if(target==0) return 1;
        else return 0;
    }
    if(target==0) return 0;
    if(dp[i][target]!=-1) return dp[i][target];
    int ways=0;
    for(int k=1;k<=min(cap,target);k++){
        ways=(ways+find(i+1,target-k,cap,n,dp))%mod;
    }
    return dp[i][target]=ways;
}
int Solution::findDiceSum(int A, int B, int C) {
    //vector<vector<int>> dp(A+2,vector<int>(C+1,-1));
    //return find(1,C,B,A,dp);
    vector<int> prev(C+1,0);
    prev[0]=1;
    vector<int> curr(C+1,0);
    for(int i=A;i>=1;i--){
        for(int target=1;target<=C;target++){
            int ways=0;
            for(int k=1;k<=min(B,target);k++){
                ways=(ways+prev[target-k])%mod;
            }
            curr[target]=ways;
        }
        prev=curr;
    }
    return prev[C];
}
Editor is loading...