# 1155. Number of Dice Rolls With Target Sum
###### tags: `Leetcode` `Medium` `Dynamic Programming` `Knapsack problem`
Link: https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/description/
## 思路
背包问题
## Code

class Solution {
    public int numRollsToTarget(int n, int k, int target) {
        long[][] dp = new long[n][target+1];
        int mod = 1000000007;
        for(int i=1; i<=Math.min(k, target); i++) dp[0][i] = 1;
        for(int i=1; i<n; i++){
            for(int j=0; j<=target; j++){
                if(dp[i-1][j]!=0){
                    for(int a=1; a<=k; a++){
                        if(j+a<=target) dp[i][j+a] = (dp[i][j+a]+dp[i-1][j])%mod;
                    }
                }
            }
        }
        return (int)dp[n-1][target];
    }
}