将 n 个对象分成 k 组的方法有多少种，这样任何组的对象都不会比以前形成的组少？

Question

示例： n=8, k=4 答案：5

[1,1,1,5], [1,1,2,4], [1,1,3,3], [1,2,2,3], [2,2, 2,2]

我想到了应用动态规划来计算8个对象可以分为4组的方式数，但无法理解如何跟踪上一组对象的数量。

DP 方法：

for(int j=0;j<=n;j++)
{
    for(int i=1;i<=k;i++)
    {
        if(j<i)
            continue;
        if(j==i)
            dp[j]=1;
        for(int k=1;k<i;k++)
        {
            dp[j]+=dp[k]*dp[j-k];
        }
    }
}

请帮忙解决一下。我对 DP 比较陌生。

Answer 1

根据示例，我假设没有任何组可以为空。还假设 n,k <= 1000 的值。

dp 状态将是 remaining Objects 和 remaining Groups。 f(remObject,remGroup) 将是将 remObject 放入 remGroup 的方式的数量，其中任何组的对象都不会比以前形成的组少。

我们会考虑2个案例。

如果我们想将一个对象放在最左边的组中，我们还需要将一个对象放在所有其他组中。所以我们必须确保remaining Objects >= remaining Groups。在这种情况下，我们将在答案中添加 f(remObject - remGroup, remGroup)。

如果我们不想再将任何对象放在最左边的组中，我们将在答案中添加 f(remObject,remGroup - 1)。

基本情况是没有要考虑的组并且所有对象都已放置。

由于任何组都不能为空，在调用我们的dp之前，我们将1个对象放入所有k组中。

查看代码了解更多详情。

#define mxn 1003
#define i64 long long int
#define mod 1000000007

i64 dp[mxn][mxn];

i64 f(int remObject,int remGroup) {
        if(!remGroup) {
                if(!remObject)
                        return 1;
                return 0;
        }

        if(dp[remObject][remGroup] != -1)
                return dp[remObject][remGroup];

        i64 ans = 0;
        if(remObject >= remGroup)
                ans += f(remObject - remGroup, remGroup);
        ans += f(remObject,remGroup - 1);
        ans %= mod;

         return dp[remObject][remGroup] = ans;
}

int main()
{
        int t,n,k;
        memset(dp,-1,sizeof dp);
        cin >> t;
        while(t--) {
                cin >> n >> k;
                if(n < k)
                        cout << 0 << endl;
                else
                        cout << f(n-k,k) << endl;
        }
        return 0;
}

Answer 2

更新

虽然下面的所有讨论仍然有用，但提供了一个更好的底层算法，允许我们跳过我的 min 参数。（我知道我应该查一下！）这种理解可以显着提高下面使用的算法的性能。

将动态规划 (DP) 视为一种可以加速某些递归过程的简单优化技术。如果你的递归调用是重复的（就像斐波那契数），那么存储它们的结果可以大大加快你的程序。但是底层逻辑还是递归调用。所以让我们先递归地解决这个程序，看看我们可以在哪里应用 DP 优化。

(8, 4) 只有五个解决方案足够小，即使时间在算法上是指数级的，它仍然可能是可管理的。让我们尝试一个简单的递归。首先，让我们实际构建输出而不是计算输出，以便仔细检查我们做的事情是否正确。

这个版本基于这样的想法，即我们可以设置列表的第一个数字，跟踪该值作为剩余元素的最小值，然后重复剩余位置。最后，我们用更高的初始数字再试一次。因此，除了我们的 n 和 k 输入，我们还需要保留一个 min 参数，我们从 1.

开始

这是一个版本：

const f = (n, k, min = 1) => 
  k < 1 || n < k * min
    ? []
  : k == 1
    ? [[n]]
  : [
      ... f (n - min, k - 1, min) .map (xs => [min, ...xs]), 
      ... f (n, k, min + 1)
    ]

console .log (
  f (8, 4) //~> [[1, 1, 1, 5], [1, 1, 2, 4], [1, 1, 3, 3], [1, 2, 2, 3], [2, 2, 2, 2]]
)

(你没有指定语言标签，如果JavascriptES6语法不清晰，我们可以改写成另一种风格。)

既然这样，我们可以写一个更简单的版本来计算结果：

const f = (n, k, min = 1) => 
  k < 1 || n < k * min
    ? 0
  : k == 1
    ? 1
  : f (n - min, k - 1, min) + f (n, k, min + 1)

console .log (
  f (8, 4) //~> 5
)

但是如果我们要尝试更大的集合，比如 f(1000, 10)（经检查，应该是 886745696653253¹），可能需要一点时间的时间来计算。我们的算法可能是指数级的。因此，我们可以通过两种方式进行动态规划。最明显的是 自下而上 方法：

const f = (_n, _k, _min = 1) => {
  const cache = {}
  for (let n = 1; n <= _n; n ++) {
    for (let k = 1; k <= Math.min(_k, n); k++) {
      for (let min = n; min >= 0; min--) {
        cache [n] = cache[n] || {}
        cache [n] [k] = cache [n] [k] || {}
        cache [n] [k] [min] = 
          k < 1 || n < k * min
            ? 0
            : k == 1
               ? 1
               : cache [n - min] [k - 1] [min]  + cache [n] [k] [min + 1]
      }
    }
  }
  return cache [_n] [_k] [_min]
}

console.time('time taken')
console .log (
  f (1000, 10) //~> 886745696653253
)
console.timeEnd('time taken')

在这里找出正确的边界是棘手的，如果没有其他原因的话，因为递归是基于 min 的递增值。我们很可能正在计算一路上不需要的东西。

也是丑陋的代码，失去了原始的优雅和可读性，而只获得了性能。

我们仍然可以通过记忆我们的函数来保持优雅；这是 自上而下 方法。通过使用可重用的 memoize 函数，我们可以几乎完整地使用我们的递归解决方案：

const memoize = (makeKey, fn) => {
  const cache = {}
  return (...args) => {
    const key = makeKey(...args)
    return cache[key] || (cache[key] = fn(...args))
  }
}

const makeKey = (n, k, min) => `${n}-${k}-${min}`        
        
const f = memoize(makeKey, (n, k, min = 1) => 
  k < 1 || n < k * min
    ? 0
  : k == 1
    ? 1
  : f (n - min, k - 1, min)  + f (n, k, min + 1)
)

console.time('time taken')
console .log (
  f (1000, 10) //~> 886745696653253
)
console.timeEnd('time taken')

memoize 将在每次调用时计算其结果的函数转变为仅在第一次看到特定输入集时计算结果的函数。此版本要求您提供一个附加函数，将参数转换为唯一键。还有其他的写法，但它们有点难看。这里我们只是将 (8, 4, 1) 转换为 "8-4-1"，然后将结果存储在该键下。没有歧义。下次我们调用 (8, 4, 1) 时，已经计算的结果将立即从缓存中返回。

注意有试一试的诱惑

const f = (...args) => {...}
const g = memoize(createKey, f)

但是如果 f 中的递归调用指向 f，这将不起作用。如果他们指向 g，我们已经混淆了实现并且 f 不再是独立的，所以没有什么理由这样做。因此我们把它写成memomize(createKey, (...args) => {...})。 offer alternatives 的高级技术超出了此处的讨论范围。

在自下而上的 DP 和自上而下的 DP 之间做出选择是一个复杂的问题。在上面的例子中，您会看到对于给定的输入，自下而上的版本运行得更快。附加函数调用有一些递归开销，在某些情况下您可能会受到递归深度限制。但这有时完全被自上而下的技术完全抵消，只计算你需要什么。自下而上将计算所有较小的输入（对于 "smaller" 的某些定义）以找到您的价值。自上而下只会计算解决问题所需的那些值。

¹笑话！我是用动态规划才找到这个值的

Answer 3

这些被称为 partitions with restricted number of parts。循环背后的想法，等于最大部分为 k 的分区数（证据留作简短有趣的阅读）是如果分区的最小部分为 1，我们添加了1 将 n - 1 的所有分区分成 k - 1 部分（保证最小部分为 1）；如果最小的部分不是 1，我们将 n - k 的所有分区中的每个 k 部分都加 1 到 k 部分（保证每个部分都大于 1）。

这是一个简单的记忆：

function f(n, k, memo={}){
  if (k == 0 && n == 0)
    return 1

  if (n <= 0 || k <= 0)
    return 0

  let key = String([n, k]) // Thanks to comment by user633183

  if (memo.hasOwnProperty(key))
    return memo[key]

  return memo[key] = f(n - k, k, memo) + f(n - 1, k - 1, memo)
}

console.time('time taken')
console.log(f(1000, 10))
console.timeEnd('time taken')

这是自下而上的：

function f(n, k){
  let dp = new Array(n + 1)
  for (let i=0; i<n+1; i++)
    dp[i] = new Array(k + 1).fill(0)
  dp[0][0] = 1
  
  for (let i=1; i<=n; i++)
    for (let j=1; j<=Math.min(i, k); j++)
      dp[i][j] = dp[i - j][j] + dp[i - 1][j - 1]

  return dp[n][k]
}

console.time('time taken')
console.log(f(1000, 10))
console.timeEnd('time taken')

Answer 4

可以通过添加一些检查来进一步改进记忆解决方案。如果 n,k 相等，则答案为 1。我们不需要对 1000,1000 进行递归。同样 k 是 1，无论 n 是多少，答案都是 1。1000,1 是 1，因此可以节省内存和时间。更新代码：由于声誉低下，无法将其添加为上述解决方案的评论，抱歉。你也可以在这里找到简单的解释： N into K groups recursion。

function f(n, k, memo = {}) {
    if (k == 0 && n == 0) return 1;
    if (k == 1 && n != 0) return 1; //when k is 1 no matter what n is
    if (n == k) return 1; // when k and n are equal.

    if (n <= 0 || k <= 0) return 0;

    let key = String([n, k]); // Thanks to comment by user633183

    if (memo.hasOwnProperty(key)) return memo[key];


    return (memo[key] = f(n - k, k, memo) + f(n - 1, k - 1, memo));
}

将 n 个对象分成 k 组的方法有多少种，这样任何组的对象都不会比以前形成的组少？

Number of ways to divide n objects in k groups, such that no group will have fewer objects than previously formed groups?

algorithm

recursion

dynamic-programming

memoization

更新