语言不可知 - 如何改进此动态规划解决方案(算法优化)

Question

问题陈述：

搬家保证公司(ACM(是一家为人们搬家的公司。最近，一些学校希望将计算机转移到另一个地方。所以他们要求ACM帮助他们。一所学校预留了K辆卡车用于移动，并且有N台计算机可以移动。为了不浪费卡车，学校要求ACM使用所有的卡车。也就是说，每辆卡车必须有一些电脑，没有空卡车。ACM 想知道用 K 卡车移动 N 台计算机时存在多少个分区 sheme，ACM 要求您计算给定 N 和 K 的不同 sheme 的数量。你不需要关心订单。例如 N=7，K=3，以下 3 个分区实例被视为同一个实例，应计为一个 sheme："1 1 5"，"1 5 1"，"5 1 1"。每辆卡车几乎可以携带无限的电脑！！

节省时间 ：

你必须计算有多少个序列 a[1..k] 存在，以便：

1( a[i] + a[2] +

.... + a[k] = N 使得排列无关紧要

我的 O(N*K^2( 解决方案(无法弄清楚如何改进它(

#include<assert.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
int DP[5001][5001];
void ini()
{
    int i,j,k;
    DP[0][0]=1;
    for(k=1;k<=500;k++)
        for(j=1;j<=500;j++)
           for(i=1;i<=500;i++)
            {
                DP[i][j]+=j>=k?DP[i-1][j-k]:0;
                DP[i][j]%=1988;
            }
    return ;
}
int main()
{
    ini();
    int N,K,i,j;
    while(1)
    {
        scanf("%d%d",&N,&K);
        if(N==0 && K==0)
            return 0;
        int i;
        if(DP[K][N]==0)
        {assert(0);}
        printf("%dn",DP[K][N]);
    }
    return 0;
}

我的解决方案的解释 DP[i][j] 表示我只能使用 i 卡车拥有总共 j 台计算机的方式数量。k 表示我正在处理的计算机数量，这意味着我只是在避免排列！

如何将其改进为 O(N*K(？

问题约束

N (1<=N<=

5000( 和 K(1<=K<=N(

问题

链接：问题间谍

Answer 1

就说你有K个礼品盒和N个巧克力。

我将从一个递归的和真正容易将其转换为迭代解决方案开始。

避免重复的关键是按升序分发巧克力(降序也可以(。所以你 7 块巧克力，我在第一个盒子里放 2 块巧克力，我会在第二个盒子里至少放 2 块。为什么？这有助于避免重复。

         now onwards TCL = totalChocholatesLeft & TBL  = totalBinsLeft
         So S(TCL,TBL) =  S(TCL-TBL,TBL) + S(TCL,TBL-1);
         you have to call the above expression starting with S(n-k), k)
         Why? because all boxes need at least one item so first put `1` each box. 
         Now you are left with only `n-k` chocolates.

就是这样！这就是 DP 递归。

它是如何工作的？

        So in order to remove repetitions we are maintaning the ascending order.
        What is the easiest way to maintain the ascending order ? 

如果您在第 i 个盒子里放 1 块巧克力

，请在它前面的所有盒子里放 1 块巧克力i+1, i++2 .....k.所以把巧克力放在礼品盒里后，你有两个选择：

要么你想继续当前框：

                S(TCL-TBL,TBL) covers this

或者移动下一个框，永远不要再考虑这个框

                S(TCL,TBL-1) covers this.

等效的DP将使TC：O(NK)

Answer 2

此问题等效于将n-k相同的球(在每个单元格中放置一个球以确保它不为空之后(放在k相同的单元格中。

这可以使用递归公式解决：

D(n,0) = 0       n > 0
D(n,k) = 0       n < 0
D(n,1) = 1       n >= 0
D(n,k) = D(n,k-1) + D(n-k,k)

解释：

停止条款：

• D(n，0( - 无法将 n>0 个球放入 0 个单元格中
• D(n<0，k( - 无法在 k 个单元格中放入负数球
• D(n，1( - 将 n 个球放入 1 个单元格的一种方法：全部在此单元格中

复发：

我们有两个选择。

1. 我们要么有一个(或多个(空单元格，所以我们递归相同的问题，少一个单元格：D(n,k-1)
2. 否则，我们没有空单元格，所以我们在每个单元格中放一个球，用相同数量的单元格递归，减少 k 个球，D(n-k,k)

这两种可能性是不相交集合的，因此两个集合的并集是两个大小的总和，因此D(n,k) = D(n,k-1) + D(n-k,k)

上面的递归公式在O(1)中很容易计算(假设O(1)算术(，如果已知"较低"的问题，并且DP解决方案需要填充大小为(n+1)*(k+1)的表，所以这个解决方案是O(nk)