算法笔记动态规划递归做法

今天药忘吃喽~ 2022-06-01 00:54 186阅读 0赞

1.  什么是动态规划
    
    动态规划是一种用来解决一类最优化问题的算法思想。简单来说，动态规划将一个复杂的问题分解成若干个子问题，通过综合子问题的最优解来得到原问题打的最优解。需要注意的是，动态规划会将每个求解过的子问题的解记录下来，这样当下一次碰到同样的子问题时，就可以直接使用之前记录的结果，而不是重复计算。注意：虽然动态规划采用这种方式来提高计算效率，但不能说这种做法就是动态规划的核心。  
    一般可以使用递归或者递推来实现动态规划，其中递归写法在此处又称作记忆化搜索。
2.  动态规划的递归写法  
    先来讲递归写法，通过这部分的学习，应该可以理解如何*记录子问题的解，来避免下次遇到相同的子问题时的重复计算的。*  
    以斐波那契数列为例，斐波那契数列的定义为F0 = 1,F1 = 1,Fn = Fn-1+Fn-2(n >= 2)

int F(int n){
        if(n == 0 || n ==1) return 1;
        else return F(n - 1) + F(n - 2);
    }

事实上，这个递归会涉及很多重复的计算。当n == 5时，可以得到F(5) = F(4) + F(3)，接下来在计算F(4) 时又会有F(4) = F(3) + F(2)。这时候如果不采取措施，F(3)会被计算两次。可以推知，如果n很大，重复计算的次数将难以想象。事实上，由于没有及时保存中间计算的结果，每次都会计算F(n-1)和F(n-2)这两个分支，基本不能承受n较大的情况。  
为了避免重复计算，可以开一个一维数组dp，用以保存已经计算过的结果，其中dp\[n\]记录F\[n\]的结果，并用dp\[n\] = -1表示F\[n\]当前还没有被计算过。

int dp[MAXN];

然后就可以在递归当中判断dp\[n\]是否是-1，说明已经计算过F(n)，直接返回dp\[n\]就是结果；否则，按照递归式进行递归。代码如下：

int F(int n){
        if(n == 0 || n == 1) return 1;
        if(dp[n] != -1) return dp[n];
        else{
            dp[n] = F(n - 1) + F(n - 2);
            return dp[n];
        }
    }

这样就把已经计算过的内容记录了下来，于是当下再碰到需要计算相同的内容时，就能直接使用上次计算的结果，这可以省去大半无效计算，而这也是记忆化搜索这个名字的由来。通过记忆化搜索，把复杂度从指数级别降到了线性级别。  
通过上面的例子可以引申出一个概念：如果一个问题可以被分解成若干个子问题，且这些子问题会重复出现，那么就称这个问题拥有重叠子问题。动态规划通过记录重叠子问题的解，来使下次碰到相同的子问题时直接使用之前记录的结果，以此避免大量重复计算。因此，一个问题必须拥有重复子问题，才能使用动态规划去解决。  
![这里写图片描述][SouthEast]

> 摘自与《算法笔记》胡凡，曾磊主编

[SouthEast]: /images/20220601/ed1b05574d8f4f19835972ed389e87b7.png