DAG 上的动态规划:
有向无环图上的动态规划是学习 DP 的基础, 很多问题都可以转化为 DAG 上的最长路, 最短路或路径计数问题.
1. 没有明确固定起点重点的 DAG 模型:
嵌套矩形问题: 有 n 个矩形, 每个矩形可以用两个整数 a,b 表示它的长和宽, 矩形可以嵌套在矩形中当且仅当 a<c,b<d 或者 b<c,a<d. 选出尽量多的矩形排成一行, 使得除了最后一个之外, 每个矩形都可以嵌套在下一个矩形内. 如果有多解矩形编号字典序应尽量小.
- /**
- * 嵌套矩形问题: 有 n 个矩形, 每个矩形可以用两个整数 a,b 表示它的长和宽,
- * 矩形可以嵌套在矩形中当且仅当 a<c,b<d 或者 b<c,a<d. 选出尽量多的矩形排成一行, 使得除了最后一个之外, 每个矩形都可以嵌套在下一个矩形内. 如果有多解矩形编号字典序应尽量小.
- */
- static int[] d= {-1,-1,-1,-1,-1,-1};
- static int[][]a=new int[6][6];
- public static void getA(ErYuan[] es) {// 建立单向无环图
- for(int i=0;i<es.length;i++) {
- for(int j=0;j<es.length;j++) {
- if(es[i].isOk(es[j])) {
- a[i][j]=1;
- }
- }
- }
- }
- public static int dp(int i) {// 从 i 开始的最大嵌套矩形个数
- if(d[i]>=0) {
- return d[i];
- }
- d[i]=0;
- for(int j=0;j<d.length;j++) {
- if(a[i][j]==1) {
- d[i]=Math.max(d[i],1+dp(j));
- }
- }
- return d[i];
- }
- public static void test(int i,String head) {// 找到 d[i] 中的最大值, 按字典序输出路径们
- head=head+i;
- if(d[i]==0)
- {
- System.out.println(head);
- }
- String str="";
- for(int j=0;j<d.length;j++) {
- if(a[i][j]==1&&d[i]==d[j]+1) {
- test(j,head);
- }
- }
- }
- public static void main(String[] args) {
- Scanner scn=new Scanner(System.in);
- ErYuan[] es=new ErYuan[6];
- for(int i=0;i<6;i++) {
- int x=scn.nextInt();
- int y=scn.nextInt();
- es[i]=new ErYuan(x,y);
- }
- getA(es);
- for(int i=0;i<d.length;i++) {
- dp(i);
- }
- int max=0;
- for(int i=1;i<d.length;i++) {
- max=d[max]>=d[i]?max:i;
- }
- for(int i=max;i<d.length;i++) {
- if(d[i]==d[max]) {
- test(i,"");
- }
- }
- }
- class ErYuan{
- int x;
- int y;
- public boolean isOk(ErYuan e) {
- if((x<e.x&&y<e.y)||(e.x>y&&e.y>x)){
- return true;
- }
- return false;
- }
- public ErYuan(int x, int y) {
- super();
- this.x = x;
- this.y = y;
- }
- }
2. 固定终点的最长路和最短路
硬币问题: 有 n 种硬币, 面值分别为 v1..vn, 每种都有无限多, 给定非负整数 S. 可以选用多少个硬币, 使得面值之和恰好为 S? 输出硬币的最小值和最大值 1<=n<100,0<=S<=10000,1<=vi<=S
- static int[]d=new int[10];
- static int[]vis=new int[10];
- static int[]v=new int[5];
- /**
- * 硬币问题: 有 n 种硬币, 面值分别为 v1..vn, 每种都有无限多, 给定非负整数 S.
- * 可以选用多少个硬币, 使得面值之和恰好为 S?
- */
- /**
- * S->0 的路径长度
- * @param S
- */
- public static int dp(int S) {
- if(vis[S]==1)return d[S];
- vis[S]=1;
- for(int i=0;i<vis.length;i++)if(vis[i]<=S)d[S]=Math.max(d[S], dp(S-vis[i])+1);
- return d[S];
- }
如果要打印出来就同上, 可以用递推或者储存的方式打印出来, 储存的话用空间换取时间.
3. 小结
传统的递推法可以表示成 "对于每个状态 i, 计算 f(i)", 或者称为 "填表法". 这需要对于每个状态 i, 找到 f(i) 依赖的所有状态.
刷表法: 对于每个状态 i, 更新 f(i) 所影响的状态. 只有当每个状态所依赖的对它的影响相互独立时才能用刷表法.
来源: http://www.bubuko.com/infodetail-3487930.html