【算法】整数的拆分

题目：

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

例如：
n=4，则输出5.因为4只有如下五种求和方式：
4 = 4
4 = 3 + 1
4 = 2 + 2
4 = 2 + 1 + 1
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);
	}
}

用dfs写的

public class 数的拆分 {
	public static void main(String[] args) {
		int[] data=new int[100];
		f(6,0,data);
	}

	private static void f(int m, int k,int[] data) {
		if(m==0)
		{
			for (int i = 0; i < k; i++) {
				System.out.print(data[i]+" ");
			}
			System.out.println();
		}
		
		for (int i = m; i > 0; i--) {
			if(k>0 && data[k-1]<i)continue;
			data[k]=i;
			f(m-i,k+1,data);
		}
	}
}