分月饼

标题：分月饼 | 时间限制：1秒 | 内存限制：262144K | 语言限制：不限

题目描述：

中秋节，公司分月饼，m个员工，买了n个月饼，m<=n，每个员工至少分1个月饼，但可以分多个，单人分到最多月饼的个数是Max1，单人分到第二多月饼个数是Max2，Max1-Max2 <= 3，单人分到第n-1多月饼个数是Max(n-1)，单人分到第n多月饼个数是Max(n)，Max(n-1) – Max(n) <= 3, 问有多少种分月饼的方法？

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int m = input.nextInt();
        int n = input.nextInt();
        int nm = n - m;
        int total = 0;
        if(m > n){
            System.out.println(0);
            return;
        }
        for (int i = 0; i < nm; i++){
            total = total + mooncake(m - 1, nm - i, i);
        }
        System.out.println(total);
    }
    public static int mooncake(int m, int nm, int k){
        if (nm <= 0){
            return 0;
        }
        if (m <= 0){
            return 0;
        }
        if (m == 1){
            if(nm >= k && nm <= k + 3){
                return 1;
            }
            return 0;
        }
        int total = 0;
        for (int i = k; i <= k + 3; i++){
           total = total + mooncake(m - 1, nm - i, i);
        }
        return total;
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            int person = scanner.nextInt();
            int num = scanner.nextInt();
            System.out.println(getNum(person, num));
        }
    }
    private static int getNum(int person, int num) {
        int result = 0;
        if (person == num) {
            result = 1;
        } else {
            for (int i = 1; i < num - person + 2; i++) {
                if (person * i > num) {
                    break;
                }
                result += getMax(num - i, person - 1, i);
            }
        }
        return result;
    }

    private static int getMax(int num, int person, int max) {
        if (person == 0 && num == 0) {
            return  1;
        }
        if (num < 0 || person < 0) {
            return 0;
        }
        int res = 0;
        for (int i = 0; i < 4; i++) {
            int moonCake = max + i;
            if (moonCake * person > num) {
                break;
            }
            res += getMax(num - moonCake, person - 1, moonCake);
        }
        return res;
    }
}
//manfen

import functools

@functools.lru_cache
def calc_count(n,m,last_max):
    if m==0 and n==0:
        return 1
    if n<0 or m <0:
        return 0

    comb_count=0
    moon_cakes=[last_max+i for i in range(4)]
    for mc in moon_cakes:
        if mc*m>n:
            break
        comb_count += calc_count(n-mc,m-1,mc)
    return comb_count

def main(m,n):
    if m==n:
        return 1
    else:
        comb_count=0
        for i in range(1,n-m+2):
            if m*i>n:
                break
            comb_count+=calc_count(n-i,m-1,i)
        return comb_count


if __name__=='__main__':
    while True:
        try:
            m,n=map(int,input().split())
            print(main(m,n))
        except:
            break