PKU 1221(UNIMODAL PALINDROMIC DECOMPOSITIONS)的动态规划解法(JAVA实现)
我没有区分清楚动态规划和递归的区别!下面dp是动态规划,dp1是递归,dp1会超时!
?
package problem1221;import java.util.Scanner;public class Main {private static final int MAXNUM = 300;private static long [][] mat = new long[MAXNUM][MAXNUM];/** * @param args */public static void main(String[] args) {// TODO Auto-generated method stubfor(int i = 0; i < MAXNUM; i++){for(int j = 0; j < MAXNUM; j++)mat[i][j] = -1;}Scanner scanner = new Scanner(System.in);int val;while(true){val = scanner.nextInt();if(val == 0)break;System.out.println(val + " " + solve(val));}}private static long solve(int val) {// TODO Auto-generated method stubreturn dp(val, 1);}private static long dp(int val, int below){if(val == 0)return 1;else if(val < below)return 0;else if(val == below)return 1;else{if(mat[val][below] >= 0)return mat[val][below];else{long result = dp(val - 2 * below, below) + dp(val, below + 1);mat[val][below] = result;return result;}}}private static long dp1(int val, int below){if(mat[val][below] >= 0)return mat[val][below];long result = 0;if(val == 0)result = 1;else{if(below <= val)result++;while(true){if(2 * below > val)break;result += dp1(val - 2 * below, below);below++;}}mat[val][below] = result;return result;}}