permutation - 用长度为 s 和 t 的木棍填充长度为 L 的洞的方法

Question

我需要帮助来修改我针对编程挑战提出的解决方案。问题陈述如下:

马达加斯加的斑马马丁(电影)想要填补海滩边缘 build 的小屋地板上留下的洞。该洞的长度为 L，马丁有许多木 block ，其中一些长度为 s，另一些长度为 t。由于马丁很心烦意乱，他想知道有多少种方法可以通过随意放置木 block 来填补这个洞。

输入规范
输入的唯一一行包含三个整数 L、s 和 t，用空格分隔(1 <= L, s, t <= 10^6, s != t)。

输出规范
一行以不同的方式填充孔模 10^9 + 7 (1000000007)。

示例输入
6 2 3

示例输出
2

我提交的解决方案，使用这个函数来计数:

#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;
}

问题在于，这仅计算可以完全填补漏洞的不同集合，例如:

假设我们有一个长度为 L = 6 的洞和长度为 s = 1 和 t = 2 的木棍，我的函数返回 4。这是我的函数正在计算的四组:

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

但是它需要的是这个集合的所有排列，因此应该返回 13，即:

{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}

如何修改我的函数来计算所有排列？有没有任何 Material 可以帮助我了解如何为此类问题构建动态规划解决方案？

Answer 1

让d[i] - 填充长度为 i 的洞的方法数

然后d[i] = d[i-s] + d[i-t]

d[0] = 1

d[i < 0] = 0显然