洛谷--P1028 数的计算

——————————————————————————————————————————————————
方法1：递归（超时）

import java.util.Scanner;

public class Main {
	static int n;
	static int res = 1;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		sc.close();
		
		f(n);
		System.out.println(res);
	}

	private static void f(int n) {
		for(int i = 1;i <= n / 2;i++) {//i表示左边加上的数
			res++;
			f(i);//只递归最左边的数即可
		}
	}
}

方法2：动态规划
状态表示：
dp[i] : i 的结果数
初始化：因为自身也算，所以dp[ ] 全都初始化为 1。
状态转移方程：
dp[i] : 它左边可以加的数 j 是 1—i/2，而每个数 j 又可以继续在左边加数，也就是每个 j 都对应 dp[j] 个结果，所以 dp[i] 需要累加上每个 dp[j] 。

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int n;
	static int[] dp;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		sc.close();
		
		dp = new int[n + 1];
		Arrays.fill(dp, 1);
		for(int i = 1;i <= n;i++) {
			for(int j = 1;j <= i / 2;j++) {//j是左边新加的数
				dp[i] += dp[j];
			}
		}
		System.out.println(dp[n]);
	}
}