如何改进这个动态规划解决方案（算法优化）

Question

问题陈述：

Assurance Company of Moving (ACM) 是一家为人们搬家的公司。最近，一些学校想把他们的电脑搬到另一个地方。所以他们请求 ACM 帮助他们。一所学校预留了K辆卡车搬家，它有N台电脑要搬家。为了不浪费卡车，学校要求ACM使用所有的卡车。也就是说，每辆货车里肯定有一些电脑，不能有空货车。 ACM 想知道用 K 辆卡车移动 N 台计算机时存在多少个分区 shemes，ACM 要求您计算给定 N 和 K 的不同 shemes 的数量。您不必关心顺序。例如N=7,K=3，下面3个partition instance被认为是同一个，应该算作一个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("%d\n",DP[K][N]);
    }
    return 0;
}

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

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

问题约束

N (1<=N<=5000) and K(1<=K<=N)

问题Link：Problem Spoj

Answer 1

这个问题等同于在 k 个相同的单元格中放置 n-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 个单元格的一种方法：全部放在这个单元格中

重复：

我们有两个选择。

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

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

上面的递归公式在O(1)中很容易计算（假设O(1)个算术），如果"lower"个问题已知，DP解需要补一个table 的大小 (n+1)*(k+1)，所以这个解决方案是 O(nk)

Answer 2

就说你有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)

如何改进这个动态规划解决方案（算法优化）

How to improve this Dynamic programming solution(Optimisation in algorithm)

language-agnostic

algorithm

dynamic-programming