Ways to fill a hole of length L with sticks of lengths s and t

Question

I need help to modify the solution I came up with for a programming challenge. The problem statement says as follows:

Martin the zebra of Madagascar (the movie) wants to fill the hole that's left to cover in the floor of the hut that is building in the edge of the beach. The hole has length L and Martin has many pieces of wood, some with length s and others with length t. As Martin is very distracted he wants to know in how many ways the hole can be filled by putting pieces of wood at will.

Input specification
The only line of input contains three integers L, s and t separated with a space (1 <= L, s, t <= 10^6, s != t).

Output specification
A line with the number of different ways to fill the hole modulo 10^9 + 7 (1000000007).

Sample input
6 2 3

Sample output
2

The solution I submitted, uses this function to count:

#include <iostream>
#include <vector>

using namespace std;

int ** create(int n, int m) {
  int ** a = new int*[
  for (int i = 0; i < n; i++) {
    a[i] = new int[m]; 
    a[i][0] = 1; // I assumed there is one way to fill a hole of length zero
  }
  return a;
}

int count(vector<int>  stick, int n, int m) { // Counts ways to fill the hole
  int ** fill = create(n + 1, m + 1);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      if (j < stick[i - 1])
        fill[i][j] = fill[i - 1][j] % 1000000007;
      else
        fill[i][j] = (fill[i - 1][j] + fill[i][j - stick[i - 1]]) %   1000000007;
  return fill[n][m];
}

int main() {
  int l, a, b;
  cin >> l >> a >> b;
  vector<int> stick{a, b};
  cout << count(stick, stick.size(), l) << endl;
  return 0;
}

The problem is that this only counts the different sets that can fill the hole completely, for example:

Say we have a hole of length L = 6 and sticks of lengths s = 1 and t = 2, my function returns 4. This are the four sets that my function is counting:

{1, 1, 1, 1, 1, 1}
{1, 1, 1, 1, 2}
{1, 1, 2, 2}
{2, 2, 2}

But what it's required are all the permutations of this sets, hence this should return 13, that is:

{1, 1, 1, 1, 1, 1}
{1, 1, 1, 1, 2}
{1, 1, 1, 2, 1}
{1, 1, 2, 1, 1}
{1, 2, 1, 1, 1}
{2, 1, 1, 1, 1}
{1, 1, 2, 2}
{1, 2, 1, 2}
{2, 1, 1, 2}
{1, 2, 2, 1}
{2, 1, 2, 1}
{2, 2, 1, 1}
{2, 2, 2}

How can I modify my function to count all the permutations? Is there any material that can help me understand how to build a dynamic programming solutions for this kind of problems?

Answer 1

let d[i] - number of ways to fill the hole of length i

then d[i] = d[i-s] + d[i-t]

d[0] = 1

d[i < 0] = 0 obviously