美文网首页
动态规划之放苹果

动态规划之放苹果

作者: 故梦_三笙 | 来源:发表于2019-05-09 12:31 被阅读0次

题目描述

把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同一种分法。

分析

设dp(m,n) 为m个苹果,n个盘子的放法数目,则先对n作讨论,
当n>m:必定有n-m个盘子永远空着,去掉它们对摆放苹果方法数目不产生影响。即if(n>m) dp(m,n) = dp(m,m)
当n<=m:不同的放法可以分成两类:
1、有至少一个盘子空着,即相当于dp(m,n) =dp(m,n-1);
2、所有盘子都有苹果,相当于可以从每个盘子中拿掉一个苹果,不影响不同放法的数目,即dp(m,n) = dp(m-n,n).
而总的放苹果的放法数目等于两者的和,即 dp(m,n) =dp(m,n-1)+dp(m-n,n)

#include<stdio.h>
int apple(int m,int n)
{
    if(m==0)//没有苹果的话就是一种
        return 1;
    if(n==1)//一个盘子也只有一种
        return 1;
    if(n>m)//盘子多
        return apple(m,m);
    else//盘子少
        return apple(m-n,n)+apple(m,n-1);
}
int main()
{
    int m,n;
    while(scanf("%d %d",&m,&n)!=EOF)
    {
        printf("%d\n",apple(m,n));
    }
    return 0;
}

相关文章

  • 动态规划之放苹果

    题目描述 把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,...

  • 动态规划-放苹果

    设f(m,n)为m个苹果,n个盘子的放法数目,则先对n作讨论,* 当n>m:必定有n-m个盘子永远空着,去掉它们对...

  • 4. 动态规划算法

    1. 动态规划算法总结2. 漫画:什么是动态规划?3.算法之动态规划4. 动态规划-算法

  • 2018-11-14

    今天学了动态规划一些知识,着重看了一下动态规划之背包算法(主要是0-1算法和部分算法),关于动态规划的问题重点是建...

  • 算法之【动态规划】详解(python)

    算法之动态规划详解 定义 动态规划其实是一种运筹学方法,是在多轮决策过程中寻找最优解的方法。 应用场景 动态规划问...

  • Algorithm进阶计划 -- 动态规划(上)

    动态规划动态规划的基本原理动态规划的运用 1. 动态规划的基本原理 动态规划(Dynamic Programmi...

  • [动态规划]Leetcode 1143.最长公共子序列

    如果读者对于动态规划思路解法还不是很了解,可以查阅我之前的一篇博文《算法之【动态规划】详解》,很详细的介绍了动态规...

  • 最优化模型

    数据挖掘之优化模型 1.1数学规划模型 线性规划、整数线性规划、非线性规划、多目标规划、动态规划。 1.2微分方程...

  • 动态规划 Dynamic Programming

    从运筹学和算法的角度综合介绍动态规划 算法分类总结动态规划与静态规划的关系浅析静态规划和动态规划动态规划解非线性规...

  • 动态规划之数组

    动态规划是从初始值算到目标值。递归是从目标值推到初始值。1.Given an integer array with...

网友评论

      本文标题:动态规划之放苹果

      本文链接:https://www.haomeiwen.com/subject/axhwoqtx.html