[算法]放苹果问题

小咪咪 2022-05-23 07:56 193阅读 0赞

1. 在说放苹果问题之前，先说下斐波那契数列递归求解时的时间复杂度。

由公式f(n) = f(n - 1) + f(n - 2)很容易画出其递归树：

![20180605110027798][]

每个节点都会调用一次f(n)，满二叉树节点数m = 2^h - 1，h是树高度。

则O(n) = 2^N.

2.放苹果问题

## 题目描述 ##

把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。

递归解法：

public static int fun(int m, int n) {
            if (m < 0) return 0;
            if (n == 1 || m == 0) return 1;//只有一个盘子时只有1中放法；没有苹果时也只有一种放法——全空
            return fun(m, n - 1) + fun(m - n, n);//至少有1个空盘子；全都是满盘子
        }

动态规划解法：

public static int fun2(int m, int n) {
            int[][] dp = new int[m + 1][n + 1];
            for (int i = 1; i <= m; i++) {
                dp[i][1] = 1;
            }
            for (int i = 1; i <= n; i++) {
                dp[1][i] = 1;
                dp[0][i] = 1;
            }
            
            for (int i = 2; i <= m; i++) {
                for (int j = 2; j <= n; j++) {
                    if (i >= j) {
                        dp[i][j] = dp[i][j - 1] + dp[i - j][j];
                    } else {
                        dp[i][j] = dp[i][j - 1];
                    }
                }
            }
            return dp[m][n];
        }

[20180605110027798]: /images/20220523/3161a5119cb74f4c923ee157c43905a7.png

发表评论取消回复

表情：

评论列表（有 0 条评论，193人围观）

还没有评论，来说两句吧...

相关阅读

相关《程序设计与算法（二）算法基础》《第二周递归》放苹果 1664

1664:放苹果 [查看][Link 1] [提交][Link 2] [统计][Link 3] [提示][Link 4] [提问][Link

╰+哭是因爲堅強的太久メ/ 2023年08月17日 16:23/ 0 赞/ 85 阅读

相关从放苹果问题到零钱兑换问题（动态规划）

放苹果问题题目描述 > 把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。 >

ゞ浴缸里的玫瑰/ 2023年01月15日 15:27/ 0 赞/ 163 阅读

相关放苹果（C++牛客网）

解题思路：（1）动态规划（2）空也是一种放法 include<iostream> include<vector> using namespac

Bertha 。/ 2022年11月12日 09:40/ 0 赞/ 117 阅读

相关 [编程题]放苹果

> Talk is cheap, show me the code. 一、问题描述把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？

╰半橙微兮°/ 2022年09月30日 12:53/ 0 赞/ 150 阅读

相关递归放苹果问题和整数划分问题

放苹果问题对于m个苹果，n个盘子f(m,n): 如果m<n，那么就跟m个盘子，m个苹果是一样的f(m,m)。如果m>n，那么有两种情况:一种有空盘子的情况，一种没有空

布满荆棘的人生/ 2022年06月13日 06:30/ 0 赞/ 156 阅读

相关放苹果（递归）

1664:放苹果总时间限制: 1000ms 内存限制: 65536kB 描述把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分

太过爱你忘了你带给我的痛/ 2022年06月10日 13:44/ 0 赞/ 187 阅读

相关 I - 放苹果

HPU专题训练（2）BFS&&DFS\_\_\_I - 放苹果把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1

心已赠人/ 2022年05月29日 03:54/ 0 赞/ 130 阅读

相关 [算法]放苹果问题

1. 在说放苹果问题之前，先说下斐波那契数列递归求解时的时间复杂度。由公式f(n) = f(n - 1) + f(n - 2)很容易画出其递归树： ![201806051

小咪咪/ 2022年05月23日 07:56/ 0 赞/ 194 阅读

相关 3.3 放苹果

> 将递归的问题分解为子问题来做（分类） ![70][] > 当m、n很大时，要用动态规划来做，否则会超时。 ![70 1][] ![70 2][] > 主要分为两大

迷南。/ 2022年05月09日 01:46/ 0 赞/ 177 阅读

相关 1192：放苹果

1192：放苹果时间限制: 1000 ms 内存限制: 65536 KB 提交数: 4472 通过数: 2773 【题目描述】把M个同样的苹果放在N

阳光穿透心脏的1/2处/ 2022年01月12日 02:27/ 0 赞/ 319 阅读