放苹果

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int appleNum = in.nextInt();
            int plateNum = in.nextInt();
            System.out.println(count(appleNum, plateNum));
        }
    }

    public static int count(int appleNum, int  plateNum){
        //一个盘，零个苹果
        if(appleNum == 0 || plateNum == 1){
            return 1;
        } else
        if(appleNum< plateNum){
            //盘子比苹果多
            return count(appleNum, appleNum);
        } else {
             // 情况一： 只用 b - 1个盘子
         // 情况二： 每个盘子里先放一个苹果，等价于 a - b个苹果放到 b 个盘子
            return count(appleNum, plateNum -1) + count(appleNum -plateNum, plateNum);
        }
        

    }
}
抄得大神得递归

思路有点抽象……

import java.util.Scanner; 

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int apples = in.nextInt();
        int contains = in.nextInt();
        System.out.println(getMethods(apples, contains));
    }

    public static int getMethods(int apples, int contains) {
        // 苹果数量刚好每盘子一个或者只剩最后一个盘子，计一种方法
        if (apples == 0 || contains == 1) {
            return 1;
        } 
        if (apples < 0) { // 苹果数量不够每盘子一个
            return 0;
        }
        // 每个盘子至少放了一个的情况和有若干个盘子没放的情况
        return getMethods(apples-contains, contains) + getMethods(apples, contains-1);
    }
}

package com.huawei.item.easy;

import java.util.Scanner;

public class SixtyOne {
    public static void main(String[] args) {
        //把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？
        //注意：如果有7个苹果和3个盘子，（5，1，1）和（1，5，1）被视为是同一种分法。
        Scanner in = new Scanner(System.in);
        int m = in.nextInt(); // m个苹果
        int n = in.nextInt(); // n个盘子
        int[][] dp = new int[m][n];
        int sum = uniquePaths(m, n);
        System.out.println(sum);
    }

    private static int uniquePaths(int m, int n) {
        // dp[m][n] = dp[m][n-1]+dp[m-n][n]
        int[][] dp = new int[m + 1][n + 1];
        // 初始化
        for (int i = 0; i < m + 1; i++) {
            for (int j = 0; j < n + 1; j++) {
                // 初始化数据
                if (i <= 1 || j <= 1) {
                    dp[i][j] = 1;
                    continue;
                }
                // 动态规划
                if (i < j) {
                    dp[i][j] = dp[i][j - 1];
                } else {
                    dp[i][j] = dp[i][j - 1] + dp[i - j][j];
                }
            }
        }
        return dp[m][n];
    }


}

            if (i <= 1 || j <= 1) {
                dp[i][j] = 1;
                continue;
            }

放苹果有两种情况：

1. 所有盘子都放苹果 2. 有1个或多个盘子放苹果

当苹果数量<盘子数量时，不可能所有盘子都放苹果，只能去除一个盘子，向下计算。

if (i < j) {    dp[i][j] = dp[i][j - 1];}

else {    dp[i][j] = dp[i][j - 1] + dp[i - j][j];}

//递归法
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int a = in.nextInt();
        int b = in.nextInt();
        int count = count(a, b);
        System.out.println(count);

    }
    public static int count(int a, int b) {
        if(a ==0 || b ==1){
            return 1;
        }else if(a < b){
            return count(a,a);
        }else {
            return count(a,b-1)+count(a-b,b);
        }
    }
}

import java.util.*;
//由于本体苹果是相同的，盘子也是相同的
//所以每个盘子中的苹果只区分个数，每一个放的盘子也不能分先后；
//所以我们在操作某一个盘子时只取i个苹果，但我们要保证我们分苹果的数量单调不减或者单调不增
//此处采用单调不增，即下一个盘子放的苹果数量<=当前放的苹果数量
//当前放的苹果数量不能低于剩余苹果数量平均放到剩余盘子中的数量，即(m-i)<=i*(n-1)
//递归计算，除了携带m、n之外，还需传递当前可取最大苹果数max
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(getAnswer(m, n,m));
        }
    }
    public static int getAnswer(int m,int n,int max){//max用来限制当前盘子最大能取多少个苹果
        if(n==1||m==0) {//定义只有一个盘子 或者只有0个苹果的分法
            return 1;
        }
        int answersCount = 0;
        for (int i = 1; i <= Math.min(m,max); i++) {
            if((m-i)<=i*(n-1)){
                answersCount+=getAnswer(m-i,n-1,i);
            }
        }
        return answersCount;
    }
}

import java.util.Scanner;

/**
 * 把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？
 * 注意：如果有7个苹果和3个盘子，（5，1，1）和（1，5，1）被视为是同一种分法。
 *
 *
 * 1、苹果数 < 盘子数，多余的盘子直接舍弃，因为多出来的盘子不可能放的了苹果。
 * m < n : dp[m][n] = dp[m][m]
 * 2、苹果数 >= 盘子数，那么前面盘子都放苹果，‘放到第n个盘子时’，有两种选择
 * 第n个盘子不放苹果，即舍弃第n个盘子：dp[m][n-1]
 * 第n个盘子放苹果，即到第n个盘子为止每个盘子都有苹果，所以只有m-n个苹果可以自由选择放哪些盘子里了：dp[m-n][n]
 * m >= n : dp[m][n] = dp[m-n][n]
 * 3、注意：其中苹果个数为0的dp[0][n]和盘子个数为1的dp[m][1]其放法默认初始化为1
 */
public class HJ61_dp盘子放苹果 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            dp[i][1]=1;
        }
        for (int i = 0; i <= n; i++) {
            dp[0][i]=1;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if(i<j)
                    dp[i][j]=dp[i][i];
                else
                    dp[i][j] = dp[i][j - 1] + dp[i - j][j];
            }
        }
        System.out.print(dp[m][n]);
    }
}

import java.util.Scanner;

public class Main {
    /**
        1、苹果数 < 盘子数，多余的盘子直接舍弃，因为多出来的盘子不可能放的了苹果。
            m < n : dp[m][n] = dp[m][m]
        2、苹果数 >= 盘子数，那么前面盘子都放苹果，‘放到第n个盘子时’，有两种选择
            第n个盘子不放苹果，即舍弃第n个盘子：dp[m][n-1]
            第n个盘子放苹果，即到第n个盘子为止每个盘子都有苹果，所以只有m-n个苹果可以自由选择放哪些盘子里了：dp[m-n][n]
            m >= n : dp[m][n] = dp[m-n][n]
        3、注意：其中苹果个数为0的dp[0][n]和盘子个数为1的dp[m][1]其放法默认初始化为1
    */
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int n = in.nextInt();
        int[][] dp = new int[m+1][n+1];
        for(int i=0;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(i==0 || j==1) {
                    dp[i][j] = 1;
                    continue;
                }
                if(i<j) {
                    dp[i][j] = dp[i][i];
                } else {
                    // 这里不会出现j-1=0的情况，上面当j=1的时候就已经跳过了
                    dp[i][j] = dp[i][j-1] + dp[i-j][j];  
                }
            }
        }
        System.out.print(dp[m][n]);
    }
}

我不懂怎么做，也不知道什么是动态规划，抄评论区动态规划，改了一下

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int m = Integer.parseInt(sc.next());
            int n = Integer.parseInt(sc.next());
            System.out.println(fib(m, n));
        }
    }

    static int fib(int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        return dp(dp, m, n);
    }

    static int dp(int[][] dp, int m, int n) {
        if  (m == 0 || n == 1) {
            return 1;
        }
        // 计算过不再计算
        if (dp[m][n] != 0) {
            return dp[m][n];
        }
        if (n > m) {
            dp[m][n] = dp(dp, m, n - 1);
        } else {
            dp[m][n] = dp(dp, m, n - 1) + dp(dp, m - n, n);
        }
        return dp[m][n];
    }
}

import java.util.*;
public class Main {
	static int []a=new int[11];
	static int count=0;
	static ArrayList<Integer> ans=new ArrayList<Integer>();
	public static void dfs(int num,int n) {   //num表示剩余的可以放置的苹果数
		if(ans.size()==n+1 ) {
			if(num==0)
				count++;
			return;
		}
		for(int i=0;i<=num;i++) {
			if(i>=ans.get(ans.size()-1)) {
				ans.add(i);
				dfs(num-i,n);
				ans.remove(ans.size()-1);
			}
		}
	}
	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int m=in.nextInt();
		int n=in.nextInt();
		ans.add(0);
		dfs(m,n);
		System.out.println(count);
	}

}