动态规划笔记

动态规划的原理

从做题来看我认为动态规划就是将递归的过程反向，以此来避免反复使用递归的函数进行反复的压栈，弹栈同时避免访问很多已经计算过的分支。就比如f(a) = f(a-1)+f(a-2)这个递推式，假设我们最终想要知道f(n)的值，那么我们可以使用一个递归函数f参数是i，进行递归调用。这样当然可以求出答案。但是在这个过程中涉及大量弹栈，压栈的操作，这很费时。同时例如假设我们在递归时先求的f(a-1)的值，那么至少当f(a-1)求完以后f(a-2)的值就已经被计算过一遍了，因为我们计算f(a-1)时是递归的使用f(a-1) = f(a-2) + f(a-3)。因此可以想象有大量的分支我们进行了重复的计算。为此，我们可以单纯的把每一次递归的结果保存到一个数组或者一个表中，当访问一个新的递归函数前首先访问保存递归结果的数据结构，如果已经有了结果就可以直接使用而无需再次递归。这种方式就是所谓的记忆化搜索。进一步，虽然上述过程可以避免大量的重复计算，但是当递归树的深度和广度变大时，仍会有巨量的时间用在大量的压栈弹栈上，要想解决这个问题就需要将递归函数展开到一个函数中————一般是展开成一个循环。这样递归过程就可以被抽象循环中的一段语句。这就是所谓的动态规划。
理解了动态规划要做的事后我们还有一点需要注意。上面提到动态规划需要把递归函数展开成一个循环，这一点是有条件的，因为我们所知道的循环都是延一个方向遍历的，那么如果递推关系同时要求递归双向，那么就无法进行动态规划，例如 f(a) = f(a+1)+f(a-1)。这样我们在计算f(a)值的时候就无法保证f(a+1)和f(a-1)均已被计算。因此所有具有双向递归性质的动态规划递推式均无法使用动态规划进行计算。（注意，这里的双向递归性质意思就是说必须明确的朝一个方向递归，如果递推式中有某个因素的下标是一个不确定的值x，并且这个值在某种情况下可能会超过现在要求的a，在另一些情况下有可能低于现在的a，那么也无法应用于动态规划。另外明确的朝着一个方向递归对于高维数组来说需要不同的理解，比如f(a,b) = f(a-1,b)+f(a+1,b-1)。在这个例子中虽然但看a其是双向的，但是可以发现，涉及到a+1时b是b-1，而所有的b-1在进入b的循环前均已经计算完毕，因此并不算双向的。从上面这两个例子就可以看出双向性这一概念的本质就是要求进入当前递归节点时，递推式右边的子项必须能够保证已经在之前的循环过程中全部求出）

动态规划的例题

leetcode-10:

既然要使用动态规划，那么我们就需要写出一个符合动态规划的递推式。一般的我们会先后考虑以元素和为单位进行递归，以元素作为单位进行递归。对于这一题我们设s的0-i与p的0-j是否匹配记录在dp[i][j]中，那么当s[i] == p[j]时dp[i][j]就取决于dp[i-1][j-1],而当s[i] != p[j] 时如果p[j] == '.'那么dp[i][j]也取决于dp[i-1][j-1]。否则除非p[j] == '*'，要不然dp[i][j]就必定为假。当dp[j] = '*'时，dp[i][j]是否为真就取决于p[j-1]了，如果p[j-1] = s[i],那么我们有两种选择，一种是dp[i-1][j]为真，那么由于x*可以匹配任意数量的字符x因此dp[i][j]也为真，另一种是dp[i][j-2]为真，那么由于x*也可以匹配0个字符起到空串的作用，因此dp[i][j]自然也为真。而当p[j-1] != s[i]时由于x*可以匹配空串，因此dp[i][j]取决于dp[i][j-2].综上可以总结出如下递推式：
$dp[i][j] = dp[i-1][j-1] if s[i] == p[j] || p[j] == '.' $
$= dp[i][j-2] | dp[i-1][j] if p[j] = '*' and p[j-1] == s[i] $
$= dp[i][j-2] if p[j] = '*' and p[j-1] != s[i] $
\(= false else\)
可以发现这个递推式无论在哪一维上均是单向的，因此肯定可以动态规划，直接写出代码即可：

int max(int a, int b)
{
    return a > b ? a : b;
}
bool isMatch(char * s, char * p){
    int n = strlen(s);
    int m = strlen(p);
    int** array = (int**) malloc(sizeof(int*)*(n+1));
    int i = 0 ;
    int j = 0 ;
    for(i = 0 ; i < n+1 ; i++)
    {
        array[i] = (int*) malloc(sizeof(int)*(m+1));
        memset(array[i],0,sizeof(int)*(m+1));
    }
    array[0][0] = 1;
    for(i = 0 ; i < n+1 ; i++)
    {
        for(j = 1 ; j < m+1 ; j++)
        {
            if(i == 0)
            {
                if(p[j-1] == '*')
                {
                    array[0][j] = array[0][j-2];
                }
            }
            else
            {
                if(p[j-1] == '*')
                {
                    if(p[j-2] == s[i-1] || p[j-2] == '.')
                    {
                        array[i][j] = max(array[i-1][j],array[i][j-2]);
                    }
                    else
                    {
                        array[i][j] = array[i][j-2];
                    }
                }
                else
                {
                    if(p[j-1] == s[i-1] || p[j-1] == '.')
                    {
                        array[i][j] = array[i-1][j-1];
                    }
                }
            }
        }
    }
    return array[n][m];
}