动态规划初步

2020-03-10 本文已影响0人 Ice_spring

一个递归问题例子

为了更好地理解动态规划，首先来看一个非常简单的例子。设有数列 $\{a_n\}$ 满足：
$a_1=1,a_2=1,a_n=a_{n-1}+a_{n-2},n \geq3$

试设计算法求该数列的第 $n$ 项的值。
细心的你很可能发现了，这就是 $Fibonacci$ 数列，这里它是用递归定义的，很简单地我们就能写出递归程序：

int fib(int n) {//时间复杂度是指数级别，重复计算太多
    if (n == 2) return 1;
    if (n == 1) return 1;
    return f(n - 1) + f(n - 2);
}

现在不妨来测试一下这个递归函数的性能，为了清晰地展示性能，设置全局变量 $num$ 来记录函数被调用了多少次：

#include <iostream>
#include <ctime>
using namespace std;
int num = 0;
// 递归求斐波那契数列
int fib( int n ){
    num ++;
    if( n == 1 ) return 1;
    if( n == 2 ) return 1;
    return fib(n-1) + fib(n-2);
}
int main() {
    for (int n = 10; n < 43; n++) {
        num = 0;
        time_t startTime = clock();
        int res = fib(n);
        time_t endTime = clock();
        cout << "fib(" << n << ") = " << res << endl;
        cout << "time : " << double(endTime - startTime) / CLOCKS_PER_SEC << " s" << endl;
        cout << "run function fib() " << num << " times." << endl;
        cout << endl;
    }
    return 0;
}

运行结果如下：

commonFib

可以看到这个递归函数的时间复杂度大致是指数级别的， $n$ 仅仅多 $1$ ，计算用时就几乎翻倍，函数递归时被调用次数几乎翻倍，这是为什么呢？我们以计算 $fib(5)$ 为例画出递归树：

可以看到，这个递归函数的递归过程做了很多重复计算，如我们在调用 $fib(3)$ 时调用了 $fib(2),fib(1)$ ，而调用 $fib(4)$ 时又有子过程调用了他们，这样当 $n$ 很大时，会做很多本来已经做过的计算，大量的时间开销正是在这些函数重复的递归调用上。为此我们改进我们的递归代码，加入记忆化搜索，将每次计算过的结果保存下来，即保证每个 $f(n)$ 只计算一次：

#include <iostream>
#include <ctime>
using namespace std;
int num = 0;
vector<int> memory;
int fnew(int n) {//改进的算法,记忆化搜索
    num++;//看函数被调用多少次
    if (n == 2) return 1;
    if (n == 1) return 1;
    if (memory[n] == -1)
        memory[n] = fnew(n - 1) + fnew(n - 2);
    return memory[n];
}
int main() {
    
    for (int n = 40; n < 47; n++) {
        num = 0; 
        memory = vector<int>(n + 1, -1);

        time_t startTime = clock();
        int res = fnew(n);
        time_t endTime = clock();

        cout << "fib(" << n << ") = " << res << endl;
        cout << "time : " << double(endTime - startTime) / CLOCKS_PER_SEC << " s" << endl;
        cout << "run function fib() " << num << "times." << endl; 
        cout << endl;
        memory.clear();
    }
    return 0;
}

此时的运行结果：

记忆化搜索

可以看到此时函数调用次数和没有加入记忆化搜索时根本不在一个数量级，加入记忆化搜索后时间是线性增加的，运行时间几乎可以忽略不计，甚至我们可以在很短的时间得到 $fib(100000)$ 的值(当然整数不溢出的情况下计算结果才是正确的，这里只谈时间复杂度)，而如果调用没有记忆化搜索的递归函数也许几十年都得不到结果了。

动态规划

现在终于要引出我们的动态规划了，上面的递归思路解决问题，都是自上而下的，要计算 $f(n)$ ，则需要 $f(n-1),f(n-2)$ ，计算 $f(n-1)$ ，则需要 $f(n-2),f(n-3)$ ，......，这样一直推到基本状态，而动态规划则是自下而上的，我们是按照 $f(1),f(2),f(3)...$ 这样的方向一步步计算，最终得到 $f(n)$ 。来看维基百科对动态规划的描述：

Dynamic programming( also known as dynamic optimization ) is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions——ideally, using a memory-based data structure.
将原问题拆解为若干个简单的子问题，同时解决并保存子问题的答案，使得每个子问题只被求解一次，最终获得原问题的解。

下面用动态规划的思路再来解决一下 $Fibonacci$ 数列问题(读者可以自己测试一下性能)：

int fib_d(int n) {
    vector<int>memo(n + 1, -1);
    memo[0] = 0; memo[1] = 1;
    for (int i = 2; i <= n; i++)
        memo[i] = memo[i - 1] + memo[i - 2];
    return memo[n];
}

实际上绝大多数的递归问题都可以很方便地转化为动态规划问题，只要这个递归问题具有重叠子问题和最优子结构，而且对比记忆化搜索，使用动态规划往往更加高效，因为不会涉及递归函数调用的开销。

递归类问题和动态规划的关系

动态规划问题实例

LeetCode120

普通递归方式 (这种方式最终超时)：

class Solution {//普通递归代码//超时
public:
    int calMin(vector<vector<int>>& triangle, 
        int level, int i, int j) {
        if (level == triangle.size() - 1)
            return triangle[i][j] + min(triangle[i + 1][j], triangle[i + 1][j + 1]);
        return triangle[i][j] + min(calMin(triangle, level + 1, i + 1, j), calMin(triangle, level + 1, i + 1, j + 1));
    }
    int minimumTotal(vector<vector<int>>& triangle) {
        if (triangle.size() == 0)return 0;
        if (triangle.size() == 1) return triangle[0][0];
        return calMin(triangle, 1, 0, 0);
    }
};

递归加入记忆搜索（通过）：

class Solution {//递归加入记忆搜索，通过
public:
    vector<vector<int>>memo;
    int calMin(vector<vector<int>>& triangle,
        int level, int i, int j) {
        if (level == triangle.size() - 1)//递归终止
            return triangle[i][j] + min(triangle[i + 1][j], triangle[i + 1][j + 1]);
        if (memo[i][j] == 0)
            memo[i][j] = triangle[i][j] + min(calMin(triangle, level + 1, i + 1, j),
                calMin(triangle, level + 1, i + 1, j + 1));
        return memo[i][j];
    }
    int minimumTotal(vector<vector<int>>& triangle) {
        if (triangle.size() == 0)return 0;
        if (triangle.size() == 1) return triangle[0][0];
        memo = vector<vector<int>>(triangle.size(), vector<int>());
        for (int i = 0; i < triangle.size(); i++)
            memo[i] = vector<int>(i+1, 0);
        return calMin(triangle, 1, 0, 0);
    }
};

动态规划方式：

class Solution120_2 {//动态规划
public:
    vector<vector<int>>memo;
    int minimumTotal(vector<vector<int>>& triangle) {
        if (triangle.size() == 0)return 0;
        memo = vector<vector<int>>(triangle.size(), vector<int>());
        for (int i = 0; i < triangle.size(); i++)
            memo[i] = vector<int>(i + 1, INT_MAX);
        //初始状态
        for (int i = 0; i < triangle.size(); i++)
            memo[triangle.size() - 1][i] = triangle[triangle.size() - 1][i];
        for (int i = triangle.size() - 1; i >=0; i--) {
            for (int j = triangle[i].size() - 1; j >=0; j--) {
                memo[i][j] = triangle[i][j] + min(memo[i + 1][j], memo[i + 1][j + 1]);
            }
        }

        return memo[0][0];
    }
};

LeetCode64

动态规划，我们创建一个辅助的 $memo_{m×n}$ 数组。在这个矩阵中， $memo(i, j)$ 表示从坐标 $(i,j)$ 到右下角的最小路径长度。初始化右下角的 $memo$ 值为对应的原矩阵值，然后去填整个memo数组，对于每个元素考虑移动到右边或者下面，因此获得最小路径和我们有如下递推公式：

$memo(i,j)=grid(i,j)+min(memo(i+1,j),memo(i,j+1))$

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>>memo(m, vector<int>(n,-1));
        //初始状态
        memo[m - 1][n - 1] = grid[m - 1][n - 1];
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (i == m - 1 && j != n - 1)
                    memo[i][j] = grid[i][j] + memo[i][j + 1];
                else if (j == n - 1 && i != m - 1)
                    memo[i][j] = grid[i][j] + memo[i + 1][j];
                else if (j != n - 1 && i != m - 1)
                    memo[i][j] = grid[i][j] + min(memo[i + 1][j], memo[i][j + 1]);
                
            }
        }
        return memo[0][0];
    }
};

上述代码时间复杂度 $O(mn)$ ，空间复杂度 $O(mn)$ ，实际上我们还可以进一步优化，在 $grid$ 上进行操作，这样空间复杂度只有 $O(1)$ ，比较简单，这里略去。

参考文献：
.
Thomas. 算法导论(第三版). 北京：机械工业出版社，2013.
.
刘汝佳. 算法竞赛入门. 北京：清华大学出版社，2014