当前位置： 移动技术网 > IT编程>开发语言>Java > m个苹果放在n个盘子中有多少种结果

m个苹果放在n个盘子中有多少种结果

2018年09月21日  | 移动技术网IT编程  | 我要评论

题目

m个苹果放在n个盘子中有多少种结果，前置条件：

  • 允许存在空盘
  • 重复的摆放结果忽略不计

根据题意，也就是有3种情况，的确完全重复的摆放方式是没多大意义的

思路

这题可以用枚举的描述方式进行尾递归求解：

  • 情况一：
    • 存在一个空盘，甚至没有苹果或一个苹果，直接返回 1
  • 情况二：
    • 连盘子或苹果都没有，直接返 0
  • 情况三：
    • 可能有n个盘子只摆放了一个苹果，m-n的摆放占位，剩下的苹果任意摆放
  • 情况四：
    • 可能n个盘子为空，n-1，减去这空盘，剩下的m个苹果随意放置
  • btw，存在一个以上的空盘摆放方式与图上的重复摆放方式是等价的，尾递归甚至效率并不比循环低，说了这么多，研究此类问的方法还是dp（动态规划）

将上述情况三、四二者相加就是总的所有方法（结果）

实现

package com.test.dp;

import org.junit.test;

public class appleondisktest {
    @test
    public void main(){
        system.out.println(dp(5,0));
    }

    /**
     *
     * @param m apple
     * @param n disk
     * @return
     */
    private int dp(int m,int n){
        if (m <= 0 || n <= 0)
            return 0;
        if (m == 0 || n == 1)
            return  1;
        else
        return dp(m-n,n) + dp(m,n-1);
    }
}

模拟递归的方式求解方式

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网