从暴力递归到动态规划

2016-07-04

1.前言

关于动态规划（dyamic programming 后文都用DP代替），见过很多无从下手的问题，最后用一个神奇的DP就解决了，感觉十分的神奇，感叹这个方法的强大，同时我也很费解，为什么有人能想出如此巧妙的方法？

最近看了左程云老师的书，以及听了他的算法课。其中他所讲的关于DP的章节，让我重新认识了DP，准确来说，DP不算是一种方法，而是人们长期总结出的一种优化方法。

2.DP的由来

上文中已经说了，DP是一种优化方法。为什么这么说呢，左老师的书中举了一个换钱的例子，充分说明了问题，这里我举另外一个例子，Distinct Subsequences。

一个小例子

题目大意是在母串中找能够组成子串的 子序列，返回有多少种组成方式。这题起初一看，我是想不到DP的方法，可能是题做的少吧。于是我先用暴力递归的方式来求解。

具体代码如下：

int process(string &S, string &T, int ss, int se, int ts, int te){
    if (ts > te){
        return 1;
    }
    int i;
    int res = 0;
    for (i = ss; i < se - (te - ts)+1; i++){
        if (T[ts] == S[i]){
            res += process(S, T, i+1, se, ts + 1, te);
        }
    }
    return res;
}

S是母串，T是子串
s就是start的意思，e是end的意思，ss、se、ts、te意思自然明白了。

递归过程如下：

递归返回条件为：如果ts > te，说明子串已经全部匹配完，所以返回1，算一种情况。

2.对于母串，从ss下标开始，一直到（ss - （te - ts）+1）下标结束，其中te-ts+1为子串的长度。

3.i遍历母串的每一个初始位置，如果T[ts] == S[i]，说明第一个字符匹配了，继续进入递归过程，res累加记录每次的结果。最后返回。

最后main函数调用：

1	process(S, T, 0, S.size()-1, 0, T.size()-1);

结果就是答案。

这里的暴力递归显然有很多的重复计算，所以我们可以通过记忆化的方式，将结果先保存下来。仔细观察上面的递归函数，只有参数ss和ts在变化，所以可以用一张二维的表记录下每组ss和ts对应的值，以后直接查表即可。

既然可以查表，那么自然就可以变成动态规划的问题。

代码如下:

int DPSolution(string &S, string &T){
    int i, j;
    vector<vector<int> > dp(S.size()+1, vector<int>(T.size()+1, 0));
    /*dp[i][j]的含义：
    S(0~i-1)包含多少种T(0~j-i)的组成。
    为什么是i-1和j-1，因为加入了空串的处理
    */
    for(i = 0; i <= S.size(); i++){
        dp[i][0] = 1;
    }
    for(j = 1; j <= T.size(); j++){
        dp[0][j] = 0;
    }
    for (j = 1; j <= T.size(); j++){
        for (i = j; i <= S.size(); i++){
            if (T[j-1] == S[i-1]){
                dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
            }
            else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    for (i = 0; i <= S.size(); i++){
        for (j = 0; j <= T.size(); j++){
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
    return dp[S.size()-1][T.size()-1];
}

3.总结

这是一个方法论的东西，DP的问题一般都可以分析为：
暴力递归->记忆化搜索->动态规划->空间压缩优化的动态递归 。所以说能想到暴力递归是问题的关键，当然能直接想到dp的状态转移式那是更好的。