我没有区分清楚动态规划和递归的区别!下面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 stub
for(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 stub
return 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;
}
}
分享到:
相关推荐
pku acm 第3356题 AGTC Java代码,有详细的注释,动态规划
pku动态规划题目 pku动态规划题目 pku动态规划题目 pku动态规划题目
这是pku 上所有的动态规划题目的总结,动态规划是有最优子问题和无后效性的一种算法,非常灵活。
pku 1088 java 答案,使用动态规划解决问题:
这是动态规划中经典中的经典,希望能够帮助所有爱好ACM童鞋!
pku acm 动态规划题1179解题报告
poj经典动态规划题目解题报告,包括经典的动态规划题目20多道,可以作为学习动态规划系统的资料,包括题目: Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm 1160 post office Pku ...
pku acm 1050 To the Max代码,有详细注释,动态规划
PKU中一些数据结构基本算法题的java实现,包括DIJ、PRIM、二叉查找树、并查集、动态规划、KMP、匈牙利算法、深搜广搜等
用Java代码实现POJ(PKU)上题2494!
典型的动态规划,用递归下的记忆化搜索来实现 1088 POJ 动态规划加速原理之四边形不等式 基于连通性状态压缩的动态规划问题 对一些DP题目的小结 树型动态规划 树型动态规划和状态压缩动态规划 算法导论第15章-动态...
北大ACM课件,包括动态规划、回溯、贪心等。
动态规划,算法采用动态规划算法实现以下问题: 1、 最少硬币问题(必做) (算法实现题 3-2、 http://acm.nankai.edu.cn/p1132.html) 2、 最小M段和 (算法实现题 3-11、参见P63 最大m子段和) 3、最长子序列 ...
Pku acm 第2192题 Zipper 代码,有详细的注释,动态规划
PKU Online Judge上面很全面的动态规划试题总结。动态规划是ACM考点中最重要的一大类算法之一,对于工作人员来说,动态规划也是实际开发中经常会遇到的算法。这是POJ上面很多DP题目的总结与深刻分析。利于算法学习,...
某大牛总结的动态规划学习指南,以pku题目为重点讲解,对于正迷茫于动态规划的ACM,OI选手有很大帮助。
pku2482--Stars in Your Window的源程序
pku部分题代码,不多,试一下怎么上传文件!
Pku acm 第1125题 Stockbroker Grapevine c代码,有详细的注释,动态规划,使用弗洛伊德算法