Hello, reader 👋🏽 ! Welcome to the day 2 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be solving up LeetCode's daily challenge problem. Number of dice rolls with target sum. This was an interesting problem and intuitive as well!

🤔 Problem Statement

There are n dice and each die has k faces numbered from 1 to k.

Given three integers n, k, and target, return the number of possible ways to roll the dice so the sum of the face-up numbers equals target.

For e.g., if n=1, k=6, target=3, then with 1 die we can only reach the target in 1 way by rolling a 3
If n=2, k=6, target=7, then with 2 dice we can reach 7 in the 6 following ways:
```
[1,6], [2,5], [3,4], [4,7], [5,2], [6,1]
```
Since the number can be very large, we are supposed to return the answer in mod 10^9 + 7

Link to question is here.

💬 Initial Thought process

When I read through the problem and saw the italicised sentence: the number of possible ways, I immediately thought of recursion.
I then went and tried out possibilities of choices.
For every die n, we can choose numbers from 1 to k as values in the front of die.
For e.g. when n = 2, k = 6, and target = 7 we can choose any number from 1 to 6 for all the dice.
- If we choose the 1st die front as 1, then the target for the next die would be target-1 (7-1=6).
  - Now, for the second die, there are k possible choices again such that the target would be: 5 (6-1), 4 (6-2), 3 (6-3), 2 (6-4), 1 (6-5), and 0 (6-6).
- Similarly, if we choose the 1st die front as 2, then the target for the next die would be target-2 (7-2=5).
  - Now, for the second die, there are k possible choices again such that the target would be: 4 (5-1), 3 (5-2), 2 (5-3), 1 (5-4), 0 (5-5), and -1 (5-6).
This process repeats for all the other k-2 choices of the 1st die.
With these observations, I came up with a recursion tree:
Now, let's look at the base cases.
When you reach n=0, you have no more die left to roll. At this stage there are 2 possible values for target
1. Target could be 0. That means that you have found a way to roll n dice with front to sum up the target
2. Target is greater or less than 0. That means the chosen fronts for n dice don't sum up to initial target.

👩🏽‍💻 Solution #1

Below is the solution for the above explained approach.

class NumDiceRollsWithTargetSum {
  private int mod = (int) (Math.pow(10,9)) + 7;

  public int numRollsToTarget(int n, int k, int target) {
      // No more dice to roll
      if(n == 0) {
          // You have n die fronts that sum up to initial target
          if(target == 0) {
              return 1;
          }

          // The chosen n die fronts don't sum up to initial target
          return 0;
      }

      int ways = 0;

      for(int i = 1; i<=k; i++) {
          int nextTarget = target-i;
          ways = (ways + numRollsToTarget(n-1, k, nextTarget)) % mod;
      }
      return ways % mod;
  }
}

Time Complexity: O(k^n) => for every die n, we have k choices (k calls at every level and depth of tree is at max n) (where n = number of dice)
Space Complexity: O(n) => at max we have n calls in the call stack

The issue with the above solution is that it is TC is exponential in nature and that is terrible. And if you look carefully, there are overlapping sub-problems. Multiple calls are being computed again and again.

Below image shows an example of 2 such overlapping sub-problems

💬 Thought Process for Optimisation

It's clear that for repeated sub-problems of n and target value combinations, we return the memoized result.
Now we have to optimise using Dynamic Programming. We can use a 2D data structure that holds the values for every set of n and target, and memoize results.

👩🏽‍💻 Solution 2

Below is the optimised code

class Solution {
  private int mod = (int) (Math.pow(10,9) + 7);

  public int numRollsToTarget(int n, int k, int target) {
      int[][] memoized = new int[n+1][target+1];
      for(int[] row: memoized) {
          Arrays.fill(row, -1);
      }

      return numRollsToTargetHelper(n, k, target, memoized);
  }

  private int numRollsToTargetHelper(int n, int k, int target, int[][] memoized) {
      // No more dice to roll or if the target is < 0
      // Adding this condition here because we don't want to go out of bounds.
      if(n == 0 || target < 0) {
          return (target == 0) ? 1 : 0;
      }

      // If the subproblem was already computed, return memoized result
      if(memoized[n][target] != -1) {
          return memoized[n][target] ;
      }

      int ways = 0;
      for(int i = 1; i<=k; i++) {
          int nextTarget = target-i;
          ways = (ways + numRollsToTargetHelper(n-1, k, nextTarget, memoized)) % mod;
      }
      // memoize result and return
      memoized[n][target] = ways;
      return ways;
  }
}

Time Complexity: O(n * k * target), For every value of target[j], we obtain at a die[j], we are looking at all possible k choices.
  i.e. at dice[i] (i>1), the total number of ways to reach target j = 
      (memoized[dice-1][j-1] + memoized[dice-1][j-2] + ... + memoized[dice-1][j-6])
Space Complexity: Aux space O(n * target) for memoizing results.

This can further be optimised to

Avoid implicit recursive stack space and use a bottom up DP approach/ tabulation.
Optimise space from a 2D DP to 1D DP

Although I won't be sharing these approaches here, You can find the link to the GitHub repo with these solution here.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!

1155. Number of Dice Rolls With Target Sum

Problem Solving - Day 2

Table of contents