LeetCode 1155. N ways to roll dice**

Specific ideas ：

Complete knapsack problem , Stuck in a mess ;

After seeing Sanye, I knew that it was traditional 01 The writing is not bad ;

In fact, the transmission of the past should be a ladder , But from 0 It doesn't hurt to start traversing ;

Specific code ：

class Solution {
    
public:
    int numRollsToTarget(int n, int k, int target) {
    
        int mod=1e9+7;
        vector<vector<int>>dp(n+1,vector<int>(target+1,0));
        dp[0][0]=1;
        for(int i=1;i<=n;i++){
    
            for(int j=0;j<=target;j++){
    
                for(int u=1;u<=k;u++){
    
                    if(j>=u){
    
                        dp[i][j]=(dp[i][j])%mod+(dp[i-1][j-u])%mod;
                        dp[i][j]%=mod;
                    }
                }
            }
        }
        return dp[n][target];
    }
};

class Solution {
    
public:
    int numRollsToTarget(int n, int k, int target) {
    
        if(target>k*n)
            return 0;
        int mod=1e9 + 7;
        vector<vector<int>>dp(n+1,vector<int>(target+1,0));
        dp[0][0]=1;
        for(int i=0;i<=min(k,target);i++){
    
            dp[1][i]=1;
        }
        for(int i=2;i<=n;i++){
    
            for(int j=i;j<=target;j++){
    
                for(int u=1;u<=k;u++){
    
                    if(j-u>0){
    
                        dp[i][j]=(dp[i][j])%mod+(dp[i-1][j-u])%mod;
                        dp[i][j]%=mod;
                    }
                }
            }
        }
        return dp[n][target];
    }
};