Dice Combinations ( CSES ) Problem

and Dynamic Programming Solution using tabulation and memoization in Rust Language.

Introduction

The Dice Combinations is a very similar problem to to Coin Change Problem , except that in this problem, the order of the selection also matters.

For example, in this problem, 1,2 and 2,1 is counted as different unlike Coin change problem.

So, in this problem, we have to find number of ways we can form a sum rolling dice any number of times.

For Example : If sum is 3, there are 4 ways to make it

1+1+1
1+2
2+1
3

Hence, the output should be 4.

This problem has been taken from our beloved CSES DP problem set. See Dice Combinations

Recursive Solution

In the Recursive Solution to this problem, we have to make an observation.

If we fix the first number that comes on the dice, we can calculate the number of ways by subtracting it from n and calculating recursively.

For example, if we have to find the number of ways for n = 7, then we can fix first roll as 1, 2, 3, 4, 5 and 6 and then calculate the answer recursively.

To Summarize approach,

Base Case : If the sum is less than or equal to 6, return corresponding value ( we already manually compute and store those values in an array )
Recursive Case : Return the sum of recursively calculating answer for n-1, n-2, n-3, n-4, n-5 and n-6.

Function

Here is the function using above algorithm

fn dice_combinations(sum :usize) -> usize{
    // We can make 0 in 1 and only 1 way,
    // that is by not rolling dice anymore :D
    static UPTO_6 : [usize; 7] = [1, 1, 2, 4, 8, 16, 32];

    // Base Case : If element is less than or equal to 6,
    // return corresponding value
    if sum <= 6 { return UPTO_6[sum]; }

    // Recursive Case : Else, return sum of all possible sums,
    // That is, by throwing 1, 2, 3, 4, 5 and 6.
    return (
        dice_combinations(sum-1)+dice_combinations(sum-2)+
        dice_combinations(sum-3)+dice_combinations(sum-4)+
        dice_combinations(sum-5)+dice_combinations(sum-6)
    ) % 1_000_000_007;
}

With driver code

fn dice_combinations(sum :usize) -> usize{
    // We can make 0 in 1 and only 1 way,
    // that is by not rolling dice anymore :D
    static UPTO_6 : [usize; 7] = [1, 1, 2, 4, 8, 16, 32];

    // Base Case : If element is less than or equal to 6,
    // return corresponding value
    if sum <= 6 { return UPTO_6[sum]; }

    // Recursive Case : Else, return sum of all possible sums,
    // That is, by throwing 1, 2, 3, 4, 5 and 6.
    return (
        dice_combinations(sum-1)+dice_combinations(sum-2)+
        dice_combinations(sum-3)+dice_combinations(sum-4)+
        dice_combinations(sum-5)+dice_combinations(sum-6)
    ) % 1_000_000_007;
}

// Driver Code
use std::io;

fn take_int() -> usize {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    return input.trim().parse().unwrap();
}

fn main() {
    let sum = take_int();
    println!("{}", dice_combinations(sum));
}

Input

7

Output

63

Time Complexity : O( 2ⁿ )
Space Complexity : O( n )

( Space complexity includes recursive stack space )

Overlapping Sub-problems

If we have a look carefully on recursive approach, we computed multiple results many times.

For example, if we have n = 30, then the result for n=15 is calculated thousands of times, and takes thousands of iterations each time to calculate the result.

These are called overlapping sub-problems, because it is a sub-problem of actual problem and is overlapping in multiple recursions.

To prevent this, we can store the output and each result will be calculated only once.

As the result is only dependent on sum, we can simply store the values in an array or a vector, at the index of sum itself.

For example, the result for sum = 15 will be stored at index 15.

This is called memoization or Top-down Dynamic Programming.

Memoization ( Top-down DP ) Method

In memoization method, we simply take a DP array, and store the computed result.

Algorithm

Base Case : If the stored value for given sum in DP array is not None, we return the value.
Recursive Case : Else, compute the result using recursion and store it at the index of sum.

Function

Here is the function using above algorithm

fn dice_combinations(sum :usize, dp:&mut Vec<Option<usize>>) -> usize{

    // Base Case : If result is already stored, return it
    if dp[sum].is_some() { return dp[sum].unwrap(); }

    // Recursive Case : Else, compute and return sum of all possible sums
    // That is, by throwing 1, 2, 3, 4, 5 and 6 first.

    dp[sum] = Option::from( (
        dice_combinations(sum-1, dp)+dice_combinations(sum-2, dp)+
        dice_combinations(sum-3, dp)+dice_combinations(sum-4, dp)+
        dice_combinations(sum-5, dp)+dice_combinations(sum-6, dp)
    ) % 1_000_000_007);

    return dp[sum].unwrap();
}

With driver code

fn dice_combinations(sum :usize, dp:&mut Vec<Option<usize>>) -> usize{

    // Base Case : If result is already stored, return it
    if dp[sum].is_some() { return dp[sum].unwrap(); }

    // Recursive Case : Else, compute and return sum of all possible sums
    // That is, by throwing 1, 2, 3, 4, 5 and 6 first.

    dp[sum] = Option::from( (
        dice_combinations(sum-1, dp)+dice_combinations(sum-2, dp)+
        dice_combinations(sum-3, dp)+dice_combinations(sum-4, dp)+
        dice_combinations(sum-5, dp)+dice_combinations(sum-6, dp)
    ) % 1_000_000_007);

    return dp[sum].unwrap();
}

// Driver Code
use std::io;
use std::cmp::max;

fn take_int() -> usize {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    return input.trim().parse().unwrap();
}

fn main() {
    let sum = take_int();

    // Handles the case when sum < 6 using max
    let mut dp = vec![None; max(sum+1, 7)];

    // Set values for sum upto 6
    dp[0] = Option::from(1); dp[1] = Option::from(1);
    dp[2] = Option::from(2); dp[3] = Option::from(4);
    dp[4] = Option::from(8); dp[5] = Option::from(16);
    dp[6] = Option::from(32);

    println!("{}", dice_combinations(sum, &mut dp));
}

Input

7

Output

63

Time Complexity : O( n )
Space Complexity : O( n )

Tabulation ( Bottom-up DP ) Method

Although time and space complexities of tabulation as well as memoization method are same, tabulation is much more efficient as there are a lot of expensive recursive calls in memoization.

In tabulation method, we make the array, and fill it first on the basis of base condition, and then on the basis of previously computed variables.

Algorithm

Firstly, make an array and store the results for sum upto 6.
Now, for each subsequent sum from 7 to n, set array[index] as sum of previous 6 elements.
Return the value of the array[n]

Function

Here is the function using above algorithm

fn dice_combinations(sum:usize) -> usize{
    // Handles the case when sum < 6 using max
    let mut dp = vec![0; max(sum+1, 7)];

    // Set values for sum upto 6
    dp[0] = 1; dp[1] = 1; dp[2] = 2;
    dp[3] = 4; dp[4] = 8;
    dp[5] = 16; dp[6] = 32;

    // For each value from 7 to sum,
    // set dp[sum] = sum of previous 6 elements

    for n in 7..sum+1 {
        dp[n] = (dp[n-1]+dp[n-2]+dp[n-3]+
            dp[n-4]+dp[n-5]+dp[n-6]) %1_000_000_007;
    }

    return dp[sum];
}

With Driver code

fn dice_combinations(sum:usize) -> usize{
    // Handles the case when sum < 6 using max
    let mut dp = vec![0; max(sum+1, 7)];

    // Set values for sum upto 6
    dp[0] = 1; dp[1] = 1; dp[2] = 2;
    dp[3] = 4; dp[4] = 8;
    dp[5] = 16; dp[6] = 32;

    // For each value from 7 to sum,
    // set dp[sum] = sum of previous 6 elements

    for n in 7..sum+1 {
        dp[n] = (dp[n-1]+dp[n-2]+dp[n-3]+
            dp[n-4]+dp[n-5]+dp[n-6]) %1_000_000_007;
    }

    return dp[sum];
}

// Driver Code
use std::io;
use std::cmp::max;

fn take_int() -> usize {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    return input.trim().parse().unwrap();
}

fn main() {
    let sum = take_int();

    println!("{}", dice_combinations(sum));
}

Input

7

Output

63

Time Complexity : O( n )
Space Complexity : O( n )

Space Optimized Tabulation Method

If we look tabulation method carefully, we can easily see that only previous 6 values are used to calculate the next value.

Hence, we don't have to store all the values upto n, and store only previous 6 values or 7 values, and calculate the result.

Function

Here is the function using space optimization of tabulation method.

fn dice_combinations(sum:usize) -> usize{
    // Handles the case when sum < 6 using max
    let mut dp = vec![0; 7];

    // Set values for sum upto 6
    dp[0] = 1; dp[1] = 1; dp[2] = 2;
    dp[3] = 4; dp[4] = 8;
    dp[5] = 16; dp[6] = 32;

    // if sum is less than 7, return it
    if sum < 7 {return dp[sum];}


    // Now, we first left rotate the array
    // Because we have already stored the value for n = 6
    // Hence, for n=7, first left rotate,
    // then find and store the value in dp array
    for _ in 7..sum+1 {
        // Left rotate the matrix
        for j in 0..6 {
            dp[j] = dp[j+1];
        }

        // Find and set sum as the last element of array
        dp[6] = (dp[0]+dp[1]+dp[2]+dp[3]+dp[4]+dp[5])%1000000007;
    }

    return dp[6];
}

Use the same driver code except removing the dp matrix input.

Input

7

Output

63

Time Complexity : O( n )
Space Complexity : O( 1 )

Conclusion

In Dice Combination Problem, we have to find number of ways we can form a sum by rolling dice any number of times.

In this article, we saw how to solve the dice combinations problem, first using recursion and then using Dynamic Programming, memoization as well as tabulation method, and latter the space optimized tabulation method in Rust Language.

Here is the optimized function for easy access

fn dice_combinations(sum:usize) -> usize{
    let mut dp = vec![0; 7];
    dp[0] = 1; dp[1] = 1; dp[2] = 2;
    dp[3] = 4; dp[4] = 8;
    dp[5] = 16; dp[6] = 32;
    if sum < 7 {return dp[sum];}
    for _ in 7..sum+1 { for j in 0..6 { dp[j] = dp[j+1]; }
        dp[6] = (dp[0]+dp[1]+dp[2]+dp[3]+dp[4]+dp[5])%1000000007; }
    return dp[6];
}

Thank You