# Change Dir

• 随笔 - 123
• 文章 - 0
• 评论 - 182
• 引用 - 0

• 积分 - 365337
• 排名 - 137

## 深入理解动态规划的一系列问题（12）

   1: /*
   2:  * Copyright (C) 2013 changedi
   3:  *
   4:  * Licensed under the Apache License, Version 2.0 (the "License");
   5:  * you may not use this file except in compliance with the License.
   6:  * You may obtain a copy of the License at
   7:  *
   8:  * http://www.apache.org/licenses/LICENSE-2.0
   9:  *
  10:  * Unless required by applicable law or agreed to in writing, software
  11:  * distributed under the License is distributed on an "AS IS" BASIS,
  12:  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13:  * See the License for the specific language governing permissions and
  14:  * limitations under the License.
  15:  */
  16: package com.jybat.dp;
  17:
  18: //EditDistanceProblem;
  19: public class EDP {
  20:
  21:     private static String s1 = "CAN";
  22:     private static String s2 = "ANN";
  23:     private static final int insertionCost = 1;
  24:     private static final int deletionCost = 1;
  25:     private static final int replacementCost = 1;
  26:     // it is useful to have the string lengths as symbolic constants
  27:     private static int s1Length = s1.length();
  28:     private static int s2Length = s2.length();
  29:
  30:     // The decision space is constant in this example.
  31:     // It does not depend on the current state.
  32:     // We chose to code the 3 allowed operations
  33:     // as follows:
  34:     // 1 stands for delete
  35:     // 2 stands for insert
  36:     // 12 stands for replace
  37:     private static int[] decisionSet = { 1, 2, 12 };
  38:
  39:     // costOfOperation()
  40:     // returns 0 if the specified characters in the 2 strings
  41:     // match and the decision is to perform
  42:     // "replacement" operation for matching chars
  43:     // (whose cost is usually defined as 0)
  44:     // returns 1 otherwise (if delete, insert, or a real replacement operation
  45:     // happens)
  46:     private static int costOfOperation(int i, int j, int dec) {
  47:         if (dec == 12) { // dec==12 means decision is to replace
  48:             if (s1.charAt(i - 1) // note: subtract 1 because array
  49:             // starts at index 0
  50:             == s2.charAt(j - 1)) { // matching chars, cost is 0
  51:                 return 0;
  52:             } else { // real replacement
  53:                 return replacementCost; // cost of real replacement
  54:             }
  55:         }
  56:         if (dec == 1) { // dec==1 means decision is to delete
  57:             return deletionCost;
  58:         }
  59:         // otherwise it must be that dec==2, decision to insert
  60:         return insertionCost;
  61:     }
  62:
  63:     private static int s1Adjustment(int dec) {
  64:         if (dec == 2) { // insert
  65:             return 0;
  66:         }
  67:         return 1;
  68:     }
  69:
  70:     private static int s2Adjustment(int dec) {
  71:         if (dec == 1) { // delete
  72:             return 0;
  73:         }
  74:         return 1;
  75:     }
  76:
  77:     public static int d(int i, int j) {
  78:         if (i == 0)
  79:             return j;
  80:         if (j == 0)
  81:             return i;
  82:         int min = Integer.MAX_VALUE;
  83:         for (int dec : decisionSet) {
  84:             int t = costOfOperation(i, j, dec)
  85:                     + d(i - s1Adjustment(dec), j - s2Adjustment(dec));
  86:             if (t < min)
  87:                 min = t;
  88:         }
  89:         return min;
  90:     }
  91:
  92:     /**
  93:      * @param args
  94:      */
  95:     public static void main(String[] args) {
  96:         System.out.println(d(s1Length, s2Length));
  97:
  98:     }
  99:
 100: }

DP源码如下：

   1: /*
   2:  * Copyright (C) 2013 changedi
   3:  *
   4:  * Licensed under the Apache License, Version 2.0 (the "License");
   5:  * you may not use this file except in compliance with the License.
   6:  * You may obtain a copy of the License at
   7:  *
   8:  * http://www.apache.org/licenses/LICENSE-2.0
   9:  *
  10:  * Unless required by applicable law or agreed to in writing, software
  11:  * distributed under the License is distributed on an "AS IS" BASIS,
  12:  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13:  * See the License for the specific language governing permissions and
  14:  * limitations under the License.
  15:  */
  16: package com.jybat.dp;
  17:
  18: //tower of hanoi problem
  19: //Compute the number of moves when the recursive
  20: //strategy is used.
  21: public class HANOI {
  22:
  23:     // m: number of disks to move
  24:     // i: index of source tower
  25:     // j: index of destination tower
  26:     // k: index of temporary tower
  27:     public static int f(int m, int i, int j, int k) {
  28:         if (m == 1)
  29:             return 1;
  30:         return f(m - 1, i, k, j) + f(1, i, j, k) + f(m - 1, k, j, i);
  31:     }
  32:
  33:     /**
  34:      * @param args
  35:      */
  36:     public static void main(String[] args) {
  37:         System.out.println(f(3,1,2,3));
  38:     }
  39:
  40: }

posted on 2014-05-27 10:38 changedi 阅读(1713) 评论(0)  编辑  收藏 所属分类: 算法

 只有注册用户登录后才能发表评论。 网站导航: 相关文章: