放苹果

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

}

import java.util.Scanner;
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(calculate(m,n));
        }
    }
    public static int calculate(int m,int n){
        if(m < 0 || n <= 0){
            return 0;
        }
        if(m == 1 || n == 1 || m == 0){
            return 1;
        }
        return calculate(m,n-1)+calculate(m-n,n);
    }
}

import java.util.Scanner;

public class Main {
    /*
    解析：
        放苹果情况：（1）有空盘，（2）无空盘
        有空盘理解为：f(m, n) = f(m, n-1)，在n-1个盘上放苹果，一次类推直到n==1，只有1种放法
        无空盘理解为：f(m, n) = f(m-n, n)，在n个盘上放1个苹果，剩下的m-n苹果随意放，直到m<n时，返回0，当m=n，即m-n=0时，返回1
        所以f(m, n) = f(m, n-1) + f(m-n, n);
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            System.out.println(countWays(sc.nextInt(), sc.nextInt()));
        }
    }

    // 动态规划
    public static int countWays(int m, int n) {
        // 额外创建一行作为辅助行
        int[][] dp = new int[m+1][n+1];
        // 初始化（m-n=0时，1种摆法）(n=1, 1种摆法【可省略】)
        for (int j=0; j<n+1; j++) {
            dp[0][j] = 1;
        }
        // 遍历计算（f(m, n) = f(m, n-1) + f(m-n, n)）
        for (int i=1; i<m+1; i++) {
            for (int j=1; j<n+1; j++) {
                dp[i][j] = dp[i][j-1] + (i < j ? 0 : dp[i-j][j]);
            }
        }
        return dp[m][n];
    }
}

package test;

import java.util.Scanner;

public class Temp {
//	题目描述
//	把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，
//	问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。
//	数据范围：0<=m<=10，1<=n<=10。
//	本题含有多组样例输入。
//
//	输入描述：
//	输入两个int整数
//
//	输出描述：
//	输出结果，int型

	// 分析：
//	放苹果分为两种情况，一种是有盘子为空，一种是每个盘子上都有苹果。
//	令(m,n)表示将m个苹果放入n个盘子中的摆放方法总数。
//	1.假设,m<n,有一个盘子为空，则(m,n)问题转化为将m个苹果放在n-1个盘子上，即求得(m,n-1)即可
//	2.假设,m>n,所有盘子都装有苹果，则每个盘子上至少有一个苹果，即最多剩下m-n个苹果，问题转化为将m-n个苹果放到n个盘子上
//	即求(m-n，n)

	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(count(m, n));
		}
		sc.close();
	}

	public static int count(int m, int n) {
		//不可能是负数
		if (m < 0 || n <= 0) {
			return 0;
		}
		// 细分为苹果数为1或盘子数为一的情况返回1
		//一个苹果、一个盘子、没有苹果，就都只有一种情况
		//给出了下限，1种1种的向上累计
		if (m == 1 || n == 1 || m == 0) {
			return 1;
		}
		// 将事件无线细分
		return count(m, n - 1) + count(m - n, n);
//			1.假设有一个盘子为空，则(m,n)问题转化为将m个苹果放在n-1个盘子上，即求得(m,n-1)即可
//			2.假设所有盘子都装有苹果，则每个盘子上至少有一个苹果，即最多剩下m-n个苹果，问题转化为将m-n个苹果放到n个盘子上
//			即求(m-n，n)
//			就转换为了以上两种情况
	}
}