放苹果

#include <stdio.h>
#include <string.h>
 
int f(int m, int n);
 int main()
{
    int m, n;
     while (scanf("%d %d", &m, &n) != EOF)
    {
        printf("%d\n", f(m, n));
    }
 
    return 0;
}
 
int f(int m, int n)
{
    int ret;
    if (n == 1)
    {
        ret = 1; //m个果放1个盘子 1种
    }
    else if (m == 0)
    {
        ret = 1; //0个果放n个盘子 1种
    }
    else if (m < n)
    {
        ret = f(m,m); 
        //当m<n：必定有n-m个盘子永远空着，去掉它们对摆放苹果方法数目不产生影响，
        //即if(n>m) f(m,n) = f(m,m) 问题变成m个苹果，m个盘子的问题。即下面的m>=n的情况.
    }
    else if (m >= n)
    {
        ret = f(m - n, n) + f(m, n - 1); 
        //1.至少有一个空盘f(m,n) = f(m,n-1)；
        //2.一个空盘都没有f(m,n) = f(m-n,n);(即如果所有盘子都有苹果，相当于可以从每个盘子中拿掉一个苹果，不影响不同放法的数目.
        //分析则有，总的放苹果的放法数目等于1、2两者的和，即 f(m,n) =f(m,n-1)+f(m-n,n))
    }
 
    return ret;
}

使用动态规划，设 表示有个苹果，个盘子的情况下，有多少种可能，我们可以知道总共有至多两种情况，个盘子装满和没装满，那么由于所有的苹果和盘子都是相同的，所以在盘子装满的情况下，其等于，而在没装满的情况下，至少有一个盘子没满，那么就是，因此：
状态转移方程为：

#include<iostream>

using namespace std;

int main(){

    int m,n;
    while(cin >>m && cin >> n){
        int dp[m+1][n+1];
        for(int j = 0; j <= n;j++){
            dp[0][j] = 1;
        }
        for(int i = 0; i <= m; i++){
            dp[i][0] = 0;
        }
        for(int i = 1; i<= m;i++){
            for(int j = 1; j<=n; j++){
                dp[i][j] = dp[i][j-1];
                if(i-j >= 0){
                    dp[i][j] += dp[i-j][j];
                }
            }
        }
        cout<< dp[m][n]<<endl;
    }
    return 0;
}

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 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();
        if(m<1||m>10||n<1||n>10)
            System.out.println(-1);
        else
            System.out.println(count(m,n));
        }
        in.close();
    }
    public static int count(int m,int n){
        //当苹果或盘子数目为1时，显然只有1种情况;
        //而这也是函数出口，m,n回溯到1结束，再小则没有意义
        if(m==1||n==1) return 1;
        
        //当n>m：必定有n-m个盘子永远空着，去掉它们对摆放苹果方法数目不产生影响;
        //舍去多余盘子，从m<=n的情况考虑是等价的
        if(m<n)    
            return count(m,m);
        
        //对应情况m>=n，不同的放法可以分成两类：
        //1.至少一个盘子空着，(m,n)问题转换为(m,n-1)问题;
        //2.不存在空盘子，每个盘子上至少有1个苹果，最多剩下m-n个苹果;
        //相当于把m-n个苹果放到n个盘子有几种方法，即(m,n)转换为(m-n,n)
        
        if(m==n)
            //在盘子等于苹果时，考虑情况2.没有空盘时，每个盘子刚好放一个苹果，只有1种情况
            return count(m,n-1)+1;
            
        else
            return count(m,n-1)+count(m-n,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))

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()){
            int m=sc.nextInt();
            int n=sc.nextInt();
            System.out.println(cal(m,n));
        }
    }
    
    public static int cal(int m,int n){
        int c=0;
        if(n==1){
            return 1;
        }
        for(int i=1;i<=n;i++){
            if(m<=i){
               c+=1;
               break;
            }else{
                c+=cal(m-i,i);
            }
        }
        return c;
    }
}

#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;
}

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>

using namespace std;

int f(int m,int n)
{     if(m==0 || n==1)         return 1;     if(n>m)         return f(m,m);     else         return f(m,n-1) + f(m-n,n);          }
int main()
{     int n,m;     while(cin>>m>>n)      {         if(m<0 || m>10 || n<0 || n>10)             continue;         cout<<f(m,n)<<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);
    }
}