Untitled
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...