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

Question

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

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

输入规范
输入的唯一一行包含三个整数 L、s 和 t，用 space 分隔（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 的木棍，我的函数 returns 4。这是我的函数计算的四个集合：

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

但是需要的是这个集合的所有排列，所以应该return13，即：

{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

let d[i] - 填充长度为 i

的洞的方法数

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

d[0] = 1

d[i < 0] = 0显然

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

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

permutation

dynamic-programming