暴搜时间超限，这题需要dp（完全为了做笔记，不用看我的，思路都是看前面几位的）

完全为了做笔记！！！

完全为了做笔记！！！

完全为了做笔记！！！

我也是新手，全部都是理解前面几个大佬的思路和代码

1：暴力DFS
解题思路:
    就是在每次递归中循环可能的情况，当当前值加上i大于目标值就退出，没啥好说的，这道题用这种方法也能拿到高分

参考代码:

import java.io.*;

public class Main {
	static BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter pw=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
	public static void main(String[] args) throws NumberFormatException, IOException {
		int num=Integer.parseInt(bf.readLine());
		//从start从1开始算
		int ans=dfs(1,0,num);
		pw.print(ans);
		pw.flush();
	}
	//n为目标值，sum为当前值，start为起点
	public static int  dfs(int start,int sum,int n) {
		int num=0;
		if(sum==n) return 1;
		for(int i=start;sum+i<=n;i++) {
			num+=dfs(i,sum+i,n);
		}
		return num;
	}
}

2:背包问题，dp数组做法

解题思路：

   创建一个二维数组dp[i][j]意为当前总和为i，限制最大取数为j的种类数

    从1开始遍历到这个数，再在每次遍历中取数最高为1到i的情况，如果i==j，例如3就只能分解成3，如果j==1，例如，3分解为111，那就只有1种情况

    再开始遍历其他情况，例如，3可以分解为1+2，这是分解中带上1的情况，加上是分解中最高为j的情况，就是当前情况

    再从1开始加到num，把每一种最大取值情况相加，即可得答案

参考代码：

import java.io.*;

public class Main {
	static BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter pw=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
	public static void main(String[] args) throws NumberFormatException, IOException {
		int num=Integer.parseInt(bf.readLine());
		int[][] dp=new int[num+1][num+1];
		//i表示当前总和为i，j表示选定时最高限制为j的情况
		//dp[i][j]即为当前种类数
		for(int i=1;i<=num;i++) {
			for(int j=1;j<=i;j++) {
				//如果i和j相等，只有一种情况，j=1时，只能分解成1，也就只有1种情况
				if(i==j||j==1) {
					dp[i][j]=1;
				}else {
					//第一个为分解成1和其他数的情况
					//第二个为分解成i分解掉了一个j的情况
					dp[i][j]=dp[i-1][j-1]+dp[i-j] [j];
				}
			}
		}
		int sum=0;
		//加上dp限制为1到num的各种情况
		for(int i=0;i<=num;i++) {
			sum+=dp[num][i];
		}
		pw.print(sum);
		pw.flush();
	}

}