力扣 1155. 掷骰子等于目标和的方法数(动态规划-java)

**力扣1155. 掷骰子等于目标和的方法数**

本题目要求我们找出在掷骰子时，能得到目标和的方法数。具体来说，我们有一个骰子，有六个面，每个面上都标有数字，从1到6。我们需要计算，在掷这个骰子n次后，能得到目标和的方法数。

**动态规划**

本题目可以使用动态规划来解决。动态规划是一种算法技巧，用于求解复杂问题。在这种情况下，我们可以将问题分成几个子问题，每个子问题都有一个明确的答案。然后，我们可以利用这些子问题的答案来求出最终答案。

**状态转移方程**

我们定义一个函数dp(i, j)，其中i是掷骰子的次数，j是目标和。这个函数返回在掷骰子i次后，能得到目标和j的方法数。

我们的状态转移方程如下：

* 如果i =0，则dp(i, j) =1，如果j =0；否则dp(i, j) =0。
* 如果i >0，则dp(i, j) = dp(i -1, j - k)，其中k是骰子上可能出现的数字（从1到6）。

**Java代码**

javapublic class Main {
 public static int numRollsToTarget(int n, int k, int target) {
 // 初始化dp数组 int[][] dp = new int[n +1][target +1];
 // base case for (int i =0; i <= n; i++) {
 dp[i][0] =1;
 }
 // 状态转移方程 for (int i =1; i <= n; i++) {
 for (int j =1; j <= target; j++) {
 int sum =0;
 for (int k =1; k <= Math.min(j, k); k++) {
 sum += dp[i -1][j - k];
 }
 dp[i][j] = sum;
 }
 }
 // 返回结果 return dp[n][target];
 }

 public static void main(String[] args) {
 System.out.println(numRollsToTarget(3,6,7)); // Output:15 System.out.println(numRollsToTarget(50,100,500)); // Output:1045853744 }
}

**注释**

* 在本题目中，我们使用动态规划来求解问题。我们定义一个函数dp(i, j)，其中i是掷骰子的次数，j是目标和。
* 我们的状态转移方程如下：如果i =0，则dp(i, j) =1，如果j =0；否则dp(i, j) =0。如果i >0，则dp(i, j) = dp(i -1, j - k)，其中k是骰子上可能出现的数字（从1到6）。
* 我们使用一个二维数组dp来存储状态转移方程的结果。
* 最后，我们返回dp[n][target]作为结果。

**总结**

本题目要求我们找出在掷骰子时，能得到目标和的方法数。我们使用动态规划来解决这个问题，并定义一个函数dp(i, j)，其中i是掷骰子的次数，j是目标和。我们的状态转移方程如下：如果i =0，则dp(i, j) =1，如果j =0；否则dp(i, j) =0。如果i >0，则dp(i, j) = dp(i -1, j - k)，其中k是骰子上可能出现的数字（从1到6）。我们使用一个二维数组dp来存储状态转移方程的结果。最后，我们返回dp[n][target]作为结果。