从暴力递归到动态规划

在之前的文章大家应该也接触到了一些递归的思想，递归的实质就是函数嵌套着函数，在第一个函数运行中间一定会运行多个函数，因此函数退出条件的设置一定要合理，否则会造成堆栈充满，程序异常退出！ 那我们今天来看看如何从暴力递归改成动态规划？动态规划的实质又是什么？什么情况下可以让暴力递归改成动态规划？

1

暴力递归和动态规划的区别

暴力递归：（自顶向下）

1. 首先对问题进行分而治之，将一个大问题转化为规模缩小了的同类子问题，如求f(n)是可以通过f(n-1)来求解！也就是有明确的递归式表达！
2. 由于递归不能无休止进行，那么必须有明确的退出条件（base case）
3. 当子问题有解时如何进行下一步的决策
4. 暴力递归不会记录子问题的解

比如：如果一个字符串str，我们需要打印其所有的字串，包括空字符串？ 我们可以这样考虑，我们需要对这个字符串进行遍历每个字母，然后对于每个字符我们都选择要或者不要两种情况！一直遍历到字符串结束，最后所得到的所有的结果即为该字符串的所有字串！如果你不太理解，可以自己画一个树状图来加深理解！ 问题代码：

#include <functional>
#include <string>
#include <iostream>
using namespace std;
void printAllSub(string str, int i, string res){
    if (i == str.length()){
        cout << res << endl;
        return;
    }
    printAllSub(str, i+1, res);
    printAllSub(str, i+1, res + str.at(i));
}

int main(int argv, char** argc){
    string test = "abc";
    printAllSub(test, 0, "");
}

动态规划：（自底向上）

1. 类似于递归的过程，但是会保留每个子问题的解，并且下次直接使用，不用再次计算子问题
2. 将暴力递归的每个过程都抽象成为一个状态表达，也就是每个问题的解
3. 从小到大，依次求出每个问题的解

最简单的例子是阶乘的问题，对于暴力递归来说，如果要求解8！，那么会重复的去计算7！，6！，5！等等，这样就会造成计算的重复，因此会消耗大量的时间复杂度，而对于动态规划来说，8！=8*7！，计算速度很快，由于7！的结果我已经算过了，但是相应的我们需要空间来储存这些子问题的结果，所以动态规划也不是完美的适用任何情况！因此动态规划是一种以空间换取时间的一种策略，因此在使用时要考量这个任务对于时间和空间的需求！

那么什么时候可以将暴力递归改成动态规划呢？ 一般情况下，动态规划是通过拆分问题，并将每个问题定义为每个状态，并且可以对每个状态进行递推的方式解决！因此需要三个条件：

• 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，叫做最优化原理
• 重叠的子问题：一个子问题在下一个问题中重复用到，子问题之间也不独立，这是使用动态规划的必要条件
• 无后效性：即某个阶段确定后，其状态不会受到后续决策的影响，值不会发生改变！

2

题目：矩阵的最短路径

有一个矩阵map，它每个格子有一个权值。从左上角的格子开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，返回所有的路径中最小的路径和。 测试样例： [[1, 2, 3], [1, 1, 1]] 返回：4

3

暴力递归版

对于暴力递归来说，我们首先要划分子问题，首先我们要求最短路径，那么我们首先划分子问题，如果要求左上角到（i, j）的距离，那么它跟左上角到（i-1, j）以及左上角到（i, j-1）的距离（最小值）有关！我们只需要增加递归退出条件和决策条件即可！

其缺点非常的明显了，就是存在大量的重复计算，明明已经计算过了左上角到（i, j）的距离，在下次计算左上角到（i+1, j）时还会再次重复计算，大大降低了算法的效率！

int process1(vector<vector<int>> matrix, int i, int j){  // i, j表示行数和列数
    int res = matrix[i][j];
    if(i == 0 && j == 0){
        return res;
    }
    if(i != 0 && j == 0){
        return res + process1(matrix, i - 1, j);
    }
    if(i == 0 && j !=0){
        return res + process1(matrix, i, j - 1);
    }
    return res + min(process1(matrix, i, j - 1), process1(matrix, i - 1, j)); 
}

int minPath1(vector<vector<int>> matrix){
    return process1(matrix, matrix.size()-1, matrix[0].size()-1);
}

4

动态规划版

动态规划的本质就是递归+缓存（各个子问题的解）！ 由于上面我们分析了process(i, j)只和process(i-1, j)以及process(i, j-1)两个子问题的结果有关系，并且无后效性，因此我们可以建立一个与原地图map大小一致的矩阵来储存各个子问题的结果，比如dp(i, j)表示从map的左上角（0, 0）到（i, j）的最短距离，这样就会减少大量的重复计算，也会防止因为数据大量时，多次递归会导致栈充满的缺点！

int minPath2(vector<vector<int>> matrix){
    if(matrix.size() == 0 || matrix[0].size() == 0){
        return 0;
    }
    int row = matrix.size();
    int col = matrix[0].size();
    vector<vector<int>> dp(row, vector<int>(col));  //二维vector初始化的方式
    dp[0][0] = matrix[0][0];
    for(int i = 1;i < row; i++){
        dp[i][0] = dp[i-1][0] + matrix[i][0];
    }
    for(int j = 1;j < col; j++){
        dp[0][j] = dp[0][j-1] + matrix[0][j];
    }
    for(int i = 1;i < row; i++){
        for(int j = 1;j < col; j++){
            dp[i][j] = matrix[i][j] + min(dp[i-1][j], dp[i][j-1]);
        }
    }
    return dp[row - 1][col - 1];
}

5

资源分享

以上完整代码文件（C++版）,文件名为：矩阵的最短路径.cpp，请关注我的个人公众号 （算法工程师之路），回复"左神算法基础CPP"即可获得，并实时更新！希望大家多多支持哦~

公众号简介：分享算法工程师必备技能，谈谈那些有深度有意思的算法，主要范围：C++数据结构与算法/深度学习（CV），立志成为Offer收割机！坚持分享算法题目和解题思路（Day By Day)

完

▼

更多精彩推荐，请关注我们

▼

长按二维码关注算法工程师之路

算法工程师

我们一起努力，For World!