寒假21：整数的拆分

题目：

给定一个正整数n，求一共有多少种方式将它写成若干个正整数之和。

4 = 1 + 1 + 1 + 1

第一种方法，简单递归。n的拆分，太复杂，但是如果我们限制了最多拆成几个整数之和，就简单些例如拆成一个整数：4 = 4 一种拆成两个整数：4 = 3 + 1；4 = 2 + 2 两种……

递归（记忆化）：

import java.util.Scanner;public class 整数拆分1 {	static int[][] data;	static int p(int n, int m){		System.out.PRintln(n+"+"+m);		if(n<m)return 0;				if(n==1||m==1||n==m) return 1;				if(n>m){ 			if(data[n][m]==-1)				data[n][m]=p(n-1,m-1)+p(n-m,m);			return data[n][m];		}		return 0;	}		public static void main(String[] args) {				Scanner sc = new Scanner(System.in);		int n = sc.nextInt();		data=new int[n+1][n+1];				for (int i = 0; i < n+1; i++) {			for (int j = 0; j < n+1; j++) {				data[i][j]=-1;			}		}		int result = 0;		for(int i=1; i<=n; i++){			result += p(n, i);		}		System.out.println(result);	}}动态规划：
import java.util.Scanner;public class 数的拆分dp {	static int[][] dp;	public static void main(String[] args) {				Scanner sc = new Scanner(System.in);		int n = sc.nextInt();		dp=new int[n+1][n+1];		for (int i = 1; i < n+1; i++) {			dp[i][1]=1;			dp[i][i]=1;			for (int j = 1; j < n+1; j++) {				if(i>j){					dp[i][j]=dp[i-1][j-1]+dp[i-j][j];				}			}			for (int j = 1; j < i+1; j++) {				dp[i][n]+=dp[i][j];			}						//打表			for (int j = 0; j < n+1; j++) {				System.out.print(dp[i][j]+",");			}			System.out.println();		}		System.out.println(dp[n][n]/2);	}}