LeetCode刷题【1155】掷骰子的N种方法

输入：n = 1, k = 6, target = 3
输出：1
解释：你扔一个有6张脸的骰子。
得到3的和只有一种方法。

输入：n = 2, k = 6, target = 7
输出：6
解释：你扔两个骰子，每个骰子有6个面。
得到7的和有6种方法1+6 2+5 3+4 4+3 5+2 6+1。

输入：n = 30, k = 30, target = 500
输出：222616187
解释：返回的结果必须是对 109 + 7 取模。

二维简单DP
简单DP算法，想要得到结果target，那么我们单独拿出来假定的最后一个骰子，这个骰子有1到k种可能性
继而对应在得到target之前，没有这个骰子的时候需要算出的target-1到target-k种情况的总和，
那么我们就很容易的知道了转移方程

dp[i][target] = dp[i-1][target-1] + .... + dp[i-1][target-k]

初始一个情况，只有一个骰子的时候，1到k的值都只有1种组合情况

代码

class Solution {

    /**
     * dp[i][target] = dp[i-1][target-1] + .... + dp[i-1][target-k]
     */
    public int numRollsToTarget(int n, int k, int target) {
        int mod = (int) 1e9 + 7;
        int[][] dp = new int[n][target+1];
        for (int i = 1; i <= k && i <= target; i++) {
            dp[0][i] = 1;
        }
        for (int row = 1; row < n; row++) {
            for (int col = row+1; col <= target; col++) {
                for (int i = 1; i <= k; i++) {
                    if (i>col){
                        continue;
                    }
                    dp[row][col] += dp[row-1][col-i];
                    dp[row][col] %= mod;
                }
            }
        }
        return dp[n-1][target];
    }
}