华为机试-极限法（分苹果。剪绳子）

描述

把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？

注意：如果有7个苹果和3个盘子，（5，1，1）和（1，5，1）被视为是同一种分法。

数据范围：0 \le m \le 10 \0≤m≤10 ，1 \le n \le 10 \1≤n≤10 。

输入描述：

输入两个int整数

输出描述：

输出结果，int型

示例1

输入：

7 3

复制输出：

8

思考，把苹果放盘子里面，那么就有两种情况，一种是盘子里面有苹果，也就是有1到n的情况，还有一种就是存在两个或者以上的盘子，有盘子里面没有苹果。

有两种极限情况，假设为n个苹果，m个盘子。一种有空盘子，那么就是n个苹果，放到m-1个盘子里面。或者假设所有盘子都放了一个苹果，那么就是把n-m个苹果，放m个盘子里面。

def(m,n):
    if m == 0 or n == 0:return 0
    elif m == 1 or n == 1:return 1
    return f(m,n-1) + f(m-n,n)

通过极限法去思考问题就很简单。

还有一种递归法，思考的方式是

def f(m,n):
    if m == 0 or n == 1:return 1
    elif  n > m:
       return f(m,m)
    else:
       return f(m-n,n) + f(m,n-1)

当盘子数量远大于苹果数量的时候，可以直接考虑将盘子数量减到苹果数量相等，其他的空盘子浪费测试。

另外有种模式是剪切绳子。

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

示例 1：

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/jian-sheng-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思考：剪绳子的思考方式也是极限法，比如，当绳子长度为2的时候，不需要剪，为3也不需要，当为4的时候，需要剪成2.2两部分，5的话。要剪成3.2两部分，如果是6的话，要剪成3，3才行，不能是2，4.再继续思考，如果是7的话，那就是3.4而不是2，5，所有知道，一直剪成3米最好。

import math
class Solution:
    def cuttingRope(self, n: int) -> int:
        if n <= 3:return n -1
        if  n % 3 == 1:return int(math.pow(3,(n//3) -1) * 4)
        if n % 3 == 0:return int(math.pow(3,n //3))
        return int(math.pow(3,n//3) * 2)