Dice Combinations Solution

30 August 2021

Statement

( The original statement can be found here )
Your task is to count the number of ways to construct sum n by throwing a dice one or more times. Each throw produces an outcome between 1 and 6.
For example, if n=3, there are 4 ways:

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

Input
The only input line has an integer n.

Output
Print the number of ways modulo $10^9+7$.

Constraints
1 ≤ n ≤ $10^6$
Time limit : 1.00s
Memory limit : 512MB

Example

Input :
3

Output :
4

Solution

This problem is similiar to other well known problems such as counting the number of partitions of an integer from number theory, with the peculiarity that every term in the partition is contained in the interval $[1,6]$. However, it also resembles some problems from computer science, such as coin change or the Knapsack problem, which are usually solved using dynamic programming.

For this solution, it is probably easier to think of $N$ as a bunch of blocks that can be used to build groups of towers that are partitions of $N$.

One possible way of solving this is by recursively trying to build up all possible solutions, as suggested by the following image. (For $N=2$)

We can do this by creating a function that takes the number of blocks $left$ as an argument and loops through $S=\{1,2,3,4,5,6\}$, making a recursive call with the arguments $left-i$ in each iteration. When the number of remaining blocks is zero, we have reached our base case and increment our answer by $1$ since we have just reached a solution.

This solution is still very slow because we have to compute each partition. In order to achieve a good efficiency, an observation must be made. Note that there are five scenarios when the number of blocks is five:

Place one block and compute the number of ways to place the other 4

Place two blocks and compute the number of ways to place the other 3

Place three blocks and compute the number of ways to place the other 2

Place four blocks and compute the number of ways to place the last one (which is just one)

Place five blocks and it's over

Therefore if $c$ is our function we can say the following :
$$c(5) = 1+c(4)+c(3)+c(2)+c(1)$$ $$c(4) = 1+c(3)+c(2)+c(1)$$ $$c(3) = 1+c(2)+c(1)$$ $$c(2) = 1+c(1)$$ $$c(1)=c(0)=1$$

Look at the number of times we have to compute the same values over and over again (e. g. $c(2)\: or \: c(3)$). Instead, we can use dynamic programming to help us. If we have an array of size N to store each of the values, we only have to compute them once. After we compute them, we store them and access the values in constant time.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define MAXN 1000001
#define MOD 1000000007

int DP[MAXN], n;

int compute (int left) {
    if (DP[left] != 0) {
        return DP[left];
    }
    for (int i = 1; i <= 6; i++) {
        if (left - i >= 0) {
            DP[left] += compute(left - i);
            DP[left] %= MOD;
        }
    }
    return DP[left];
}

int main() {
    cin >> n;
    memset(DP, 0, sizeof(DP));
    DP[0] = 1;
    cout << compute(n) << endl;
}

In this way, the algorithm does not take an exponential amount of time to run. In fact, it runs with a space and time complexity of $O(n)$.