放苹果

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int m = sc.nextInt();
            int n = sc.nextInt();
            
            if(m < 0 || m > 10 || n < 1 || n > 10){
                System.out.println(-1);
            }
            
            //创建二维数组保存状态
            int[][] dp = new int[m+1][n+1];
            for(int i = 0; i <= m; i++){
                dp[i][0] = dp[i][1] = 1;
            }
            
            for(int j = 2; j <= n; j++){
                for(int i = 0; i <= m; i++){
                    if(i < j){
                        dp[i][j] = dp[i][j-1];
                    } else {
                        dp[i][j] = dp[i][j-1] + dp[i-j][j];
                    }
                }
            }
            
            System.out.println(dp[m][n]);
        }
    }
}

import sys

def func1(m,n):
    dp=[[0 for x in range(m+3)] for y in range(n)]
    for i in range(1,m+3):
        dp[0][i]=1
    for i in range(n):
            dp[i][2]=1
    for i in range(1,n):
        for j in range(3,m+3):
            dp[i][j]=dp[i-1][j]+dp[i][j-i-1]
    return dp[-1][-1]

while True:
    a = sys.stdin.readline().strip()
    if a == "":
        break
    a_=a.split(" ")
    m=int(a_[0])
    n=int(a_[1])
    #m<n时，肯定有至少n-m个盘子是空的，对结果不产生影响，应当除去
    if m>=n:
        print(func1(m,n))
    else:
        print(func1(m,m))

#include <bits/stdc++.h>
using namespace std;
int fun(int n,int m)
{
    if(n==0 || m==1) return 1;
    if(n<m) return fun(n,n);
    else return (fun(n,m-1)+fun(n-m,m));
}
int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        if(n<0 || n>10 || m<1 || m>10) continue;
        cout<<fun(n,m)<<endl;
    }
    return 0;
}

public class Main{   

#include <iostream>

using namespace std;

/*  解题分析：
        设f(m,n) 为m个苹果，n个盘子的放法数目，则先对n作讨论，
        当n>m：必定有n-m个盘子永远空着，去掉它们对摆放苹果方法数目不产生影响。即if(n>m) f(m,n) = f(m,m)　　
        当n<=m：不同的放法可以分成两类：
        1、有至少一个盘子空着，即相当于f(m,n) = f(m,n-1);  
        2、所有盘子都有苹果，相当于可以从每个盘子中拿掉一个苹果，不影响不同放法的数目，即f(m,n) = f(m-n,n).
        而总的放苹果的放法数目等于两者的和，即 f(m,n) =f(m,n-1)+f(m-n,n) 
    递归出口条件说明：
        当n=1时，所有苹果都必须放在一个盘子里，所以返回１；
        当没有苹果可放时，定义为１种放法；
        递归的两条路，第一条n会逐渐减少，终会到达出口n==1; 
        第二条m会逐渐减少，因为n>m时，我们会return f(m,m)　所以终会到达出口m==0．
*/

int func(int m,int n)  //m个苹果放在n个盘子敏感词有几种方法
{
	if(m==0||n==1)  //因为我们总是让m>=n来求解的，所以m-n>=0,所以让m=0时候结束，如果改为m=1，
		return 1;    //则可能出现m-n=0的情况从而不能得到正确解    
	if(n>m)
		return func(m,m);
	else
		return func(m,n-1)+func(m-n,n);
}

int main(){
    int m, n;
    while (cin >> m >> n){
        if (m < 0 || m > 10 || n < 0 || n > 10) continue;
        cout << func(m, n) << endl;
    }
    return 0;
}

"""函数递归思想,主要表达抽象思维，计算机语言魅力在于，给定了计算路径或者规则，输入和输出就交给晶体管解决了。言归正传哈，不妨设 f(m,n) 为分法总数，接下来就是要给定计算路径了，注意这里的计算路径类似数列递推公式，给出首几项的值，求第n项递推公式，但是计算机不要求具体的计算公式，因为计算机它可以自行迭代啊！故最简单的方法，就是通过找出第n项的前几项式子，看看它们和通项式子的关系式（也就是可迭代路径），观察规律如下：

def f(m, n):

    if m == 0 or n == 1:

        return 1

    if m < n:

        return f(m, m)  

    else:

        return (f(m, n-1) + f(m-n, n))

while True:

    try:

        m, n = map(int,input().split())

        print(f(m,n))

    except:

        break

#最后，各位观众老爷们，动态规划做成了数字游戏推到，创造不易，请点赞支持，谢谢了！

/*其实这题考的是数学啊，首先当有0个苹果或者是1个盘子的时候，只有一种分法，而其他情况
可以分为两种情况讨论：
   1、m<n，则至少有n-m个盘子是空的，此时就相当于将m个苹果分到m个盘子中，此时(m,n)=(m,m)
   2、m > n,分法是两种情况分法的和，有一个空盘子和没有空盘子，即(m,n) = (m,n-1)+(m-n,n)
*/
def putApple(m,n):
    if m == 0 or n == 1:
        return 1
    if n > m:
        return putApple(m,m)
    else:
        return putApple(m,n-1) + putApple(m-n,n)
        
        
while True:
    try:
        n, m = map(int,input().split())
        print(putApple(n, m))
    except:
        break

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
	int M, N;
	while (cin >> M >> N) {
		if (M < 1 || M>10 || N < 1 || N>10) {
			cout << -1 << endl;
			continue;
		}
		vector<vector<int>> dp(M + 1, vector<int>(N + 1, 0));
		for (int i = 1; i <= N; i++) dp[0][i] = 1;
		for (int i = 1; i <= M; i++)
			for (int j = 1; j <= N; j++)
				dp[i][j] = dp[i][j - 1] + (i < j ? 0 : dp[i - j][j]);
		cout << dp[M][N] << endl;
	}
}

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int m = sc.nextInt();
            int n = sc.nextInt();
            if(m<1 || n>10){
                System.out.println(-1);
            }else{
                System.out.println(shareCount(m,n));
            }
            
        }
    }
    public static int shareCount(int m, int n){
        if(m<0){
            return 0;
        }
        if(m==1 || n==1){
            return 1;
        }
        return shareCount(m, n-1)+shareCount(m-n,n);
    }
}

#include <stdio.h>
#include <stdlib.h>
int func(int m,int n)
{
    if(n<0||m<0)
    {
        return 0;
    }
    else if(m==1||n==1)
    {
        return 1;
    }
    else
    {
        return func(m,n-1)+func(m-n,n);
    }
}

int main()
{
    int m,n;
    while(scanf("%d %d",&m,&n)!=EOF)
    {
        printf("%d\n",func(m,n));
    }
    return 0;
}

import java.util.Scanner;

public class Main{
	
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int m = in.nextInt();
            int n = in.nextInt();
            System.out.println(count(m,n));
        }
        in.close();
	}
	
	public static int count(int m,int n){
		
		if(m<0)
			return 0;
		if(m == 0 || n == 1)
			return 1;
		return count(m,n-1)+count(m-n,n);
	}
} 

/*应用动态规划*/
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			int num_apple = sc.nextInt();
			int num_panzi = sc.nextInt();
			calculate(num_apple,num_panzi);

		}
	}
	public static void calculate(int a,int b){
		int[][] count = new int[a+1][b+1];
		for(int i=0;i<=a;i++){
			count[i][1]=1;
			count[i][0]=1;
		}
		for(int j=0;j<=b;j++){
			count[1][j]=1;
			count[0][j]=1;
		}
		for(int i=2;i<=a;i++){
			for(int j=2;j<=b;j++){
				if(i>=j){
					count[i][j] = count[i-j][j]+count[i][j-1];
				}else{
					count[i][j]=count[i][j-1];
				}

			}
		}
		System.out.println(count[a][b]);
	}

}

法1：采用递归做法
其实这根将一个整数m分成n个整数之和是类似的。

设f[m][n]为将m分成最多n份的方案数，且其中的方案不重复，即每个方案前一个份的值一定不会比后面的大,序列是一个不降序列。
当m>=n时，f[m][n] = f[m][n - 1] + f[m - n][n]
f[m][n - 1]相当于第一盘子中为0，有空盘子，只用将数分成n - 1份即可。因为0不会大于任何数，相当于f[m][n - 1]中的方案前面加一个为0的盘子。
f[m - n][n]相当于在每个盘子中加一个数1，没有空盘子。因为每个盘子中加一个数1不会影响f[m][n - 1]中的方案的可行性，也不会影响f的定义。所以f[m - n][n]一定是f[m][n]的方案的一部分，即不含有0的方案数。

当m<n的时候，肯定最少有n-m个空盘子，不过幸好，这些空盘子并不影响最后的结果，因为每种方法都带有着些空盘子，剩下的问题就是把m个苹果放到m个盘子有多少种方法了。f[m][n]=f[m][m)] m<n

临界条件，递归出口要定义好
n=1时，所有苹果都放在同一个盘子里 f(m,n)=1
m<=1时，没有苹果，f(m,n)=1

public int fun(int m,int n){
    if(m<=1 || n==1){
        return 1;
    }else if(m<n){
        return fun(m,m);
    }else{
        return fun(m,n-1)+fun(m-n,n);
    }
}

法2：动态规划
当数据规模较大时，递归的方式效率很低。使用动态规划，个人认为重点在于找对状态转移方程。
f[m][n] = f[m][n - 1] + f[m - n][n];
= 1 // m<= 1 || n <= 1

public int fun(int m,int n){
    int[][] arr = new int[m+1][n+1];
    for(int i = 0; i <= m; i++){
        for(int j = 0;j<=n;j++){
            if(i<=1 || j==1){
                arr[i][j] = 1;
            }else if(i<j){
                arr[i][j] = arr[i][i];
            }else{
                arr[i][j] = arr[i][j-1]+arr[i-j][j];
            }
        }
    }
    return arr[m][n];
}