This article is participating in Python Theme Month. See the link to the event for more details

Topic describes

This is “1155. N Ways to Roll a die” from LeetCode, and the difficulty is “medium”.

Tag: “Backpack problem”, “dynamic programming”, “group backpack”

Here are d of the same dice, each of which has f faces labeled 1,2… , f.

We agree that the roll of the dice is the sum of the numbers facing up.

If the total number of points you need to roll is target, calculate how many different combinations there are (all combinations have a total of one) and return the module.

Example 1:

Input: d = 1, f = 6, target = 3 Output: 1Copy the code

Example 2:

Input: d = 2, f = 6, target = 7 Output: 6Copy the code

Example 3:

Input: d = 2, f = 5, target = 10 Output: 1Copy the code

Example 4:

Input: d = 1, f = 2, target = 3 Output: 0Copy the code

Example 5:

Input: d = 30, f = 30, target = 500 Output: 222616187Copy the code

Tip:

  • 1 <= d, f <= 30

  • 1 <= target <= 1000

Packet backpack

In the group backpack problem we mentioned, the group backpack not only “group items to choose a” situation, there are “group items must choose a” situation.

For this problem, think of each die as a set of items, and each time you have to choose one item from the set (the size of the roll is considered a specific item).

This changes the problem to: roll a die (set of items) and roll the sum (total value obtained) for the number of options.

Although, we have not specifically talked about “the number of options for the backpack problem”, the basic analysis is not fundamentally different from “the maximum value for the backpack problem”.

We can use the state definition of “group packs for maximum value” to fine-tune: means the number of options with value of, considering the previous group of items.

For convenience, we set the item group number from the beginning, so there is an obvious initialization condition.

Represents that in the case that no item group is considered, only the number of schemes with a total value of is, and the schemes with other total values do not exist.

Without losing the general consideration of how to move, that is, what decisions are made by the second group of items.

For group A, the possible options are:

  • The result on the first die is 0

  • The result on the first die is 0

    .

  • The result on the first die is 0

Is the sum of all the above possible schemes, namely:

Simple 2 d

Java code:

class Solution {
    int mod = (int)1e9+7;
    public int numRollsToTarget(int n, int m, int t) {
        int[][] f = new int[n + 1][t + 1];
        f[0] [0] = 1;
        // Enumerates item groups (per die)
        for (int i = 1; i <= n; i++) {
            // Enumerate the size of the knapsack (the total number of points thrown)
            for (int j = 0; j <= t; j++) {
                // Enumerate the decision (the number of dice currently rolled)
                for (int k = 1; k <= m; k++) {
                    if (j >= k) {
                        f[i][j] = (f[i][j] + f[i-1][j-k]) % mod; }}}}returnf[n][t]; }}Copy the code
  • Time complexity: O(n∗m∗t)O(n * m * t)O(n∗m∗t)
  • Space complexity: O(n∗t)O(n * t)O(n∗t)

Scroll to the array

According to the state transition equation, we find that it clearly depends only on, and.

So we can use the scroll array that we learned before, to optimize the space in a very mechanical way from to.

It is important to note that since we are adding schemes directly on the basis of the lattice, you must manually set them to zero.

Java code:

class Solution {
    int mod = (int)1e9+7;
    public int numRollsToTarget(int n, int m, int t) {
        int[][] f = new int[2][t + 1];
        f[0] [0] = 1;
        for (int i = 1; i <= n; i++) {
            int a = i & 1, b = (i - 1) & 1;
            for (int j = 0; j <= t; j++) {
                f[a][j] = 0; // Set to zero manually first
                for (int k = 1; k <= m; k++) {
                    if(j >= k) { f[a][j] = (f[a][j] + f[b][j-k]) % mod; }}}}return f[n&1][t]; }}Copy the code
  • Time complexity: O(n∗m∗t)O(n * m * t)O(n∗m∗t)
  • Space complexity: O(t)O(t)O(t)

One dimensional optimization

Furthermore, using the “explicitly only depends on, and”, we can optimize the one-dimensional space by “01 knapsack” : cancel the item dimension and adjust the traversal order of the capacity dimension to “from large to small”.

Java code:

class Solution {
    int mod = (int)1e9+7;
    public int numRollsToTarget(int n, int m, int t) {
        int[] f = new int[t + 1];
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = t; j >= 0; j--) {
                f[j] = 0;
                for (int k = 1; k <= m; k++) {
                    if(j >= k) { f[j] = (f[j] + f[j-k]) % mod; }}}}returnf[t]; }}Copy the code
  • Time complexity: O(n∗m∗t)O(n * m * t)O(n∗m∗t)
  • Space complexity: O(t)O(t)O(t)

conclusion

It’s not hard to see whether it’s “choose one item at most” or “choose one item at most”.

We are directly applying the basic idea of grouping backpack “enumeration item group – enumeration capacity – enumeration decision” to solve.

The spatial optimization of grouping knapsack does not reduce the time complexity, so for the grouping knapsack problem, we can write a simple multidimensional version that is convenient for debugging (if the space is acceptable), and then mechanically change to the “scrolling array” form if the card space is encountered.

In addition, today we use the “group backpack problem solution number” as a “group backpack problem for the maximum value” exercise.

As you can see, there is no essential difference between the two, and both are fine-tuned by applying the state definition of “maximizing value with the backpack problem”.

More on the number of options for the backpack problem will be covered later.

The last

This is article No.1155 in our “Brush through LeetCode” series, which began on 2021/01/01. As of the start date, there are 1916 questions on LeetCode, some with locks, and we will first brush through all the questions without locks.

In this series of articles, in addition to explaining how to solve the problem, I’ll give you the most concise code possible. If the general solution is involved, the corresponding code template will be provided.

In order to facilitate the students to debug and submit the code on the computer, I set up a related warehouse: github.com/SharingSour… .

In the repository address, you can see the solution to the series, the corresponding code to the series, the LeetCode link, and other preferred solutions to the series.