LeetCode 1155. 擲骰子的N種方法**

具體思路：

完全背包問題，被卡的一塌胡塗；

看了三葉的才知道和傳統01寫的大差不差；

其實傳遞過去應該是一個階梯形，但是從0開始遍曆無傷大雅；

具體代碼：

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];
    }
};