动态规划:一个数有有几种拆法(分盘子问题)

编辑于 2017-04-04

* 移动设备下, 可左滑手指以查看较宽代码

题目

一个数如3,可以拆成 2+1,1+1,3 这 3 种拆法,给一个数 n,求有几种拆法。

分析

相当于 m 个苹果放入 n 个盘子,有几种方法。

设 f(m,n) 为 m 个苹果,n 个盘子的放法数目,则先对 n 作讨论,

当 n>m:则必定有 n-m 个盘子永远空着,去掉它们对摆放苹果方法数目不产生影响。即 if(n>m) f(m,n) = f(m,m)

当 n <= m: 不同的放法可以分成两类:含有0(空盘子)的方案数,不含有0的方案数:

1)含有0的方案数,即有至少一个盘子空着,即相当于 f(m,n)=f(m,n-1);

2)不含有0的方案数,即所有的盘子都有苹果,相当于可以从每个盘子中拿掉一个苹果,不影响不同放法的数目,即 f(m,n)=f(m-n,n)。而总的放苹果的放法数目等于两者的和,即 f(m,n)=f(m,n-1)+f(m-n,n),这样就成功把 f(m,n) 降到了 f(m-n,n)。

当 n=1 时,所有苹果都必须放在一个盘子里,所以返回1,类似的 m = 1 时返回1,m = 0 或 n = 0 时也返回1。

递归

int fun(int m, int n) //m个苹果放在n个盘子中共有几种方法
{
    if(m==0 || n==1)
        return 1;
    if(n>m)
        return fun(m,m);
    else
        return fun(m,n-1) + fun(m-n,n);
}

动态规划

int main()
{
    int n=6;
    int i, j, dp[100][100];

    for (int i = 0; i < 100; ++i)
        dp[i][0] = dp[0][i] = 1;

    for (i = 1; i < n+1; ++i) {
        for (j = 1; j < n+1; ++j) {
            if (i == 1 || j == 1)
                dp[i][j] = 1;
            else if (i >= j)
                dp[i][j] = dp[i][j - 1] + dp[i - j][j];
            else
                dp[i][j] = dp[i][i];
        }
    }

    cout<<dp[n][n]<<endl;

    return 0;
}