动态规划，递归与非递归，FP 之野望，描述与计算

　　然后开始分析问题：如果一个句子（也是字符串）可以被完全分解为若干魔力单词的拼接，那么这个句子就是一条咒语。
    根据题目，假设要判断的字符串为c0c1..cn-1
    该字符串为咒语显然有两种情况：
　　１.c0c1..cn-1本身就是一个魔力单词，当然就是咒语
　　２.否则，存在该字符串的一个分解c0..ck1-1 ck1..ck2-1,...,ckm..cn-1使得每一段都是魔力单词。

根据这个已经可以写出暴力解法了。
不过可以更进一步的分析，在第二种情况，相当于存在一个k （1<k<n-1）将字符串分成两段，使得前一段由若干个魔力单词组成，后一段也是由若干个魔力单词组成，也就是2等价于
　　2'.否则，存在k （1<k<n-1）使得c0...ck-1与ck..cn-1都是咒语。

到这里，状态转移方程已经路出水面。我们记f(i,j)表示字符串cici+1..cj-1是否是咒语，则有：
   f(i,j) =   if(ci..cj-1 是魔力单词) true
　　　　　　   else  if 存在 i<k<j使得 f(i,k)&f(k,j) true
　　　　　　　else  false

根据这个，很容易可以写出下面的代码：

/**
    &#BrutalSolver.java
    Solver的暴力实现
    @author Eastsun
    @date 2008/6/19 1:41
*/
public class BrutalSolver implements Solver{
    public boolean isCharm(String text,MagicDict dict){
        if(dict.isMagic(text)) return true;
        for(int index =1;index <text.length();index ++){
            String left =text.substring(0,index);
            String right =text.substring(index);
            if(isCharm(left,dict)&&isCharm(right,dict)) return true;
        }
        return false;
    }
}

　　状态方程已经有了，动态规划还会远吗？
　　动态规划的核心就是避免重复计算。。。仔细想想上面的代码那些是重复计算了，很容易可以得到递归形式的动态规划实现：//未测试。。

/**
    &#RecDpSolver.java
    Solver的递归形式的动态规划实现
    @author Eastsun
    @date 2008/6/19 1:59
*/
public class RecDpSolver implements Solver{
    //用buf来保存已经计算过的
    //0 表示还没有计算
    //1表示text(i,j)是咒语
    //-1表示不是
    private int[][] buf;
    private String text;
    private MagicDict dict;
    
    public boolean isCharm(String text,MagicDict dict){
        this.text = text;
        this.dict = dict;
        int len = text.length();
        //用于保存计算结果，初始为0
        buf =new int[len+1][len+1];
        return isCharm(0,len)==1;
    }
    
    private int isCharm(int i,int j){
        //关键，计算过的不要再计算
        if(buf[i][j]!=0) return buf[i][j];
        
        if(dict.isMagic(text.substring(i,j))){
            buf[i][j] = 1;
        }
        else{
            buf[i][j] = -1;
            for(int k =i+1;k<j;k++){
                if(isCharm(i,k)==1&&isCharm(k,j)==1){
                    buf[i][j] = 1;
                    break;
                }
            }
        }
        return buf[i][j];
    }
}

在写递推代码之前，先来计算下上面DP的复杂度，根据

由于 0<=i<j<=n,所以状态数f(i,j)共有C(n,2) = n*(n+1)/2个
也就是O(n^2),决策数也就是那个for循环，为O(n)个，转移费用显然为O(1)(就是个if语句)
so，整体时间复杂度是O(n^2)*O(n)*O(1) = O(n^3)
而空间复杂度就是那个buf了，O(n^2)

居然花了这么长时间~
累了，递推的实现睡一觉再说
不过根据状态转移方程，以及状态的依赖关系，很容易写出一个有三个嵌套循环语句的递推实现来，而且其时间复杂度更容易看出来。

//--------------------------------------------------------------
睡了一觉，接着写完：
睡之前想到，其实我一开始给的那个状态转移方程还可以改进


　　其中2'可以改写为：
　　2''.否则，存在k(0<k<n-1)使得c0...ck-1是咒语，而ck..cn-1是魔力单词。
　　这样有什么好处呢？记g(i)为字符串c0c1..ci-1是否为咒语，根据改进的转移方程，显然有：
　　g(i) = if(c0c1..ci-1是魔力单词) true
　　　　　　　　else if 存在 0<k<i 使得g(k)&ck..cn-1是魔力单词 true
　　　　　　　　　　　else false

　　一个很明显的改进就是现在g(i)只有n个状态，而之前的f(i,j)有O(n^2)个状态。而且决策数与转移费用没变，所以这样就把时间复杂度由O(n^3)降低到O(n^2),空间复杂度由O(n^2)降低到O(n).很神奇吧，呵呵。
　　从这里也可以看出状态转移方程在做动态规划类的题目时有着很重要的作用……废话就不说了，还是得写出实际代码才行，下面就是使用改进过的状态转移方程得到的递归形式的DP实现：

/**
    &#RecDpSolver.java
    Solver的递归形式的动态规划实现，使用改进过的转移方程
    @author Eastsun
    @date 2008/6/19 9:54
*/
public class RecDpSolver2 implements Solver{
    
    private int[] buf;
    private String text;
    private MagicDict dict;
    
    public boolean isCharm(String text,MagicDict dict){
        this.text =text;
        this.dict =dict;
        int len =text.length();
        buf =new int[len+1];
        return isCharm(len)==1;
    }
    
    private int isCharm(int i){
        //here!!
        if(buf[i] != 0) return buf[i];
        
        //状态转移
        if(dict.isMagic(text.substring(0,i))){
            buf[i] = 1;
        }
        else{
            buf[i] = -1;
            for(int k =1;k <i;k ++)
                if(isCharm(k)==1&&dict.isMagic(text.substring(k,i))){
                    buf[i] = 1;
                    break;
                }
        }
        return buf[i];
    }
}

根据前面brute算法写的，这是暴力算法，在最好的情况下就是下面的情况，否则就跟递归的 fibs一样痛苦了：

module Main where

dict = ["hello", "world", "python", "ruby", "lisp", "haskell", "perl", "c++", "java", "c#"]

isCharm [] = False
isCharm w 
    | elem w dict = True
    | otherwise   =  or [(isCharm $ take i w) && 
                        (isCharm $ drop i w) | i <- [0 .. length w - 1 ]]

main = print $ isCharm "rubyperljavac#hellopythonworld"

我们增加调试信息，看下函数的实际调用情况：

module Main where

dict = ["hello", "world", "python", "ruby", "lisp", "haskell", "perl", "c++", "java", "c#"]

isCharm [] =    {-# SCC "empty list" #-} False
isCharm w 
    | elem w dict = {-# SCC "in dict" #-} True
    | otherwise   = {-# SCC "otherwise" #-} or [(isCharm $ take i w) && 
                                                (isCharm $ drop i w) | i <- [0 .. length w - 1 ]]

main = print $ isCharm "rubyperljavac#hellopythonworld"

增加调试信息的编译与执行：

$ ghc -prof -auto-all -o magicdict magicdict.hs
$ ./magicdict +RTS -p
True

执行后生成一个 magicdict.prof 文件，里面有每隔函数的调用次数：

$ cat magicdict.prof 
	Thu Jun 19 10:10 2008 Time and Allocation Profiling Report  (Final)

	   magicdict +RTS -p -RTS

	total time  =        0.00 secs   (0 ticks @ 20 ms)
	total alloc =      60,424 bytes  (excludes profiling overheads)

COST CENTRE                    MODULE               %time %alloc

CAF                            GHC.Handle             0.0    2.4
otherwise                      Main                   0.0   48.9
main                           Main                   0.0    1.8
isCharm                        Main                   0.0   40.0
dict                           Main                   0.0    3.0
CAF                            Main                   0.0    3.7


                                                                                               individual    inherited
COST CENTRE              MODULE                                               no.    entries  %time %alloc   %time %alloc

MAIN                     MAIN                                                   1           0   0.0    0.0     0.0  100.0
 CAF                     Main                                                 152           6   0.0    3.7     0.0   97.3
  dict                   Main                                                 160           1   0.0    3.0     0.0    3.0
  main                   Main                                                 158           1   0.0    1.8     0.0   90.6
   isCharm               Main                                                 159         155   0.0   40.0     0.0   88.8
    in dict              Main                                                 163           7   0.0    0.0     0.0    0.0
    empty list           Main                                                 162          74   0.0    0.0     0.0    0.0
    otherwise            Main                                                 161          74   0.0   48.9     0.0   48.9
 CAF                     GHC.Show                                             146           1   0.0    0.3     0.0    0.3
 CAF                     GHC.Handle                                            90           4   0.0    2.4     0.0    2.4

其中： isCharm 函数共调用 155 次，其中 in dict 7 次， 我们测试的字符串也是由7个magic word组成的，其他 empty list 发生74次 （这是递归的终止条件), otherwise情况 74次。

　　最后，将改进后的动态规划的递推形式实现。
　　动态规划的递推实现比递归实现还是要稍稍难一点，因为状态转移方程本身就是以递归的形式出现的，用递归实现当然容易了。
　　用递推实现的关键是要搞清楚状态之间的依赖关系，也就是说，那些状态应该先计算出来，那些状态是根据这些计算出来的状态算出来的。


　　这个转移方程比较简单，因为只有一个变量i。
　　很容易可以看出，要计算g(i),先得计算出g(1),...,g(i-1).
　　然后，使用递推，有一些状态必须是不依赖其他状态直接被计算出来的。这些状态称为初始状态。
　　在这里，显然g(1)是可以直接计算出来的。
　　ＯＫ，下面上代码：

/**
    &#ForDpSolver2.java
    Solver的递推形式的动态规划实现，改进之后的转移方程
    @author Eastsun
    @date 2008/6/19 10:08
*/
public class ForDpSolver2 implements Solver{
    
    public boolean isCharm(String text,MagicDict dict){
        int len =text.length();
        
        //使用递推还有一个附加的好处，就是不需要再记忆某个状态是否已经计算过
        //因为使用递推，能够保证之前的肯定计算过
        //这样可以节约空间
        boolean[] buf =new boolean[len+1];
        
        //初始化递推状态
        buf[1] = dict.isMagic(text.substring(0,1)); 
        for(int i =2;i<= len;i ++)
            for(int k=1;k< i;k ++)
                if(buf[k]&&dict.isMagic(text.substring(k,i))){
                    buf[i] = true;
                    break;
                }
        return buf[len];
    }
}

作为测试，大家可以想一想，我一开始给出的那个状态转移方程怎样用递推来实现。

动态规划可以解决T1给出的公式么?这个可是挑战极限的好例子啊,呵呵~

f(0,n)=n+1, f(m,0)=f(m-1,1), f(m,n)=f(m-1,f(m,n-1))

可以，但是仍然很慢，而且还是只能算很小的数。
暴力解法就不要发了，因为在暴力解法的基础上直接进行动态规划是没戏的，必须知道加速回溯的办法才行。其实就是一个字符串匹配算法的变形，在此基础上要多一层测试魔法字典的回溯。

广告....好大的一个广告...
请问隔壁怎么走？



难不成要做个总的巨大的咒语辞典？
或者在每次运行过程中，维护一个小的快查魔力字典？



Stay tuned.

死格格巫不过是做对米外包的，就歧视我们对倭外包的，还是赤果果的！是可忍孰不可忍？