算法学习：动态规划问题的一般解法

Posted on 2018-06-12 Edited on 2018-12-19

例题一 : Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

分析：

设三角形共有 $N$ 行， $r$ 为三角形的行， $c$ 为三角形的列。从点 $P(r,c)$ 出发，每向下走一步有两个点 $P_1(r+1,c), P_2(r+1, c+1)$ 可以选择 ,如果每次都选值小的点 $min(P1, P2)$ ，则最后得到的点的值之和即是最优解。令 $M(r,c)$ 为从 $P(r,c)$ 开始到下面的列的各条路径中，最佳路径的数字之和。

解法一：

这是一个典型的递归问题。

$M(r,c) = \begin{cases} P(r,c), & \text{if r = N }\\ min(M(r+1,c), M(r+1,c+1)) + P(r,c),& \text{others}\\ \end{cases}$

由此写出代码：

class Solution {
public:
    int getMinPathSum(vector<vector<int>>& triangle, int r, int c){
        if(r == triangle.size() - 1) return triangle[r][c];

        int x = getMinPathSum(triangle, r+1, c);
        int y = getMinPathSum(triangle, r+1, c+1);

        x = x<y ? x: y;

        return triangle[r][c] + x;
    }

    int minimumTotal(vector<vector<int>>& triangle) {
        return getMinPathSum(triangle, 0,0);
    }
};

代码没有问题，在 “Run Code” 时可以得出正确的结果。但是 “Submit” 却会给出 “Time Limit Exceeded”,超时！

如果我们推算这个解法的时间复杂度的话，可以得到 $O(2^n)$ .这不超时就有鬼了。我们需要改进这个算法。

解法二：

可以看出， $M$ (即getMinPathSum) 被重复计算了，越是靠近三角形底部、越是靠近每行的中心，重复计算的次数越多。设想：假如当我们第一次算出 $M(r,c)$ 时, 就将其保存到某个地方 $T(r,c)$ ，下次需要计算 $M(r,c)$ 的时候直接取 $T(r,c)$ ，那不就可以避免重复计算了吗，这样时间复杂度可以降到 $O(n^2)$ , 因为该三角形中的数字的总个数为 $\frac {n(n+1)}{2}$ 。如下代码：

class Solution {
public:
    struct MinVal{
        bool flag; //是否已设置了值
        int val;
        MinVal():flag(false),val(0){};
    };

    int getMinPathSum(vector<vector<int>>& triangle, int r, int c, vector<vector<MinVal>>& tmp){
        if(r == triangle.size() - 1) return triangle[r][c]; //最后一行不用保存
        if(tmp[r][c].flag) return tmp[r][c].val;

        int x = getMinPathSum(triangle, r+1, c, tmp);
        int y = getMinPathSum(triangle, r+1, c+1, tmp);

        x = x<y ? x: y;

        //算过的值，保存起来
        x = triangle[r][c] + x;
        tmp[r][c].val = x;
        tmp[r][c].flag = true;
        return x;
    }

    int minimumTotal(vector<vector<int>>& triangle) {
        //构造临时空间
        vector<vector<MinVal>> tmp(triangle.size());
        for(int i = 0; i<tmp.size(); ++i){
            tmp[i] = vector<MinVal>(triangle[i].size());
        }

        return getMinPathSum(triangle, 0,0, tmp);
    }
};

一个小结：

在解题的过程中，我们思路：

将一个求最优解的问题分解成求多个最优解的子问题 (定义 $M(r,c)$ 的过程 )
意识到子问题会重复计算
将会被重复计算的子问题的解存储起来。且不会改变。

这种求解具有 重叠子问题 的 最优解 的问题的过程中，避免子问题被重复计算而将子问题的解存储起来的算法，可以称之为 动态规划 算法。我们可把子问题叫做 状态 ，在方法二中，从求子问题的解到将子问题的解存储起来的过程，看做是从一种状态到另一状态的 转移 。
再将上面的思路总结一下，即为动态规划算法的适用性：

最优子结构性质：问题的最优解所包含了子问题的解也是最优的；
子问题重叠性质：每次产生的子问题并不总是新问题。动态规划利用该性质将每个子问题的解存储，该子问题不再进行重复计算；
状态转移无后效性质：子问题的解一旦确定，将不会再改变。

解法三：

上面的解法是自顶而下的递归解法。根据以上三个性质，我们也可以尝试自下而上的来解问题。即从最后一行开始，算出每个点的最优解，一直算到顶点，该顶点的解即是最优解：

class Solution {
public:

    int minimumTotal(vector<vector<int>>& triangle) {
        if(triangle.size() == 1) return triangle[0][0];

        //构造临时空间
        vector<vector<int>> tmp(triangle.size());
        for(int r = 0; r<tmp.size(); ++r){
            tmp[r] = vector<int>(triangle[r].size());
        }

        for(int r = triangle.size()-1; r >= 0 ; --r){
            for(int c = 0; c < triangle[r].size(); ++c){
                if(r == triangle.size() - 1){
                    tmp[r][c] = triangle[r][c];
                }
                else{
                    tmp[r][c] = triangle[r][c] + (tmp[r+1][c] < tmp[r+1][c+1] ?tmp[r+1][c] : tmp[r+1][c+1] );
                }
            }
        }
        return tmp[0][0];
    }
};

这种思路将递归的解法改造成递推的解法，更容易理解。

解法四：

解法二、三都构造了一个与三角形等大的数组。空间复杂度大大增加了( $O(r^2)$ )。可不可以改进呢？可以的，实际上，在递推的过程中，当 $T(r+1)$ 被 $M(r)$ 使用以后不会再参与计算，可以使用 $T(r)$ 覆盖 $T(r+1)$ ,这样临时空间只需要大小的 $r$ 即能完全够用。

class Solution {
public:

    int minimumTotal(vector<vector<int>>& triangle) {
        if(triangle.size() == 1) return triangle[0][0];

        //构造临时空间
        vector<int> tmp(triangle[triangle.size()-1].size());

        for(int r = triangle.size()-1; r >= 0 ; --r){
            for(int c = 0; c < triangle[r].size(); ++c){
                if(r == triangle.size() - 1){
                    tmp[c] = triangle[r][c];
                }
                else{
                    tmp[c] = triangle[r][c] + (tmp[c] < tmp[c+1] ? tmp[c] : tmp[c+1] );
                }
            }
        }

        return tmp[0];
    }
};

同理，可以再优化：当完成 $M(r,c)$ 后， $P(r, c)$ 将不再参与计算，这个空间是可以拿来利用的，可以用其来存储 $M(r,c)$ 。这样最终结果存储在 $P(0,0)$ 中。即在上面代码中，最后返回的结果是 triangle[0][0] . 代码略。

例题二：Maximum Subarray

LeetCode 53. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],

Output: 6

Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

解法一：

朴素的递归方法。

分析：求和最大的子数组。设 $S_i$ 为从 $i$ 开始的，有最大和的子数组之和，那么该问题的解即为求 $S_0, S_1, \dots , S_n$ 中的最大值。

$S_i = \begin{cases} nums[i], & \text{if } i ==n ;\\max(nums[i], nums[i] + S_{i+1}), & \text{Others} \\ \end{cases}$

相应的代码：

class Solution {
public:
    int getMaxSum(vector<int>& nums, int i){
        if(i == nums.size() - 1) return nums[nums.size()-1];

        return std::max(nums[i] + getMaxSum(nums, i+1),nums[i]);
    }

    int maxSubArray(vector<int>& nums) {
        if(nums.size() == 1) return nums[0];

        vector<int> maxs(nums.size());
        for(int i = 0; i<nums.size(); ++i){
            maxs[i] = getMaxSum(nums,i);
        }

        return *std::max_element(maxs.begin(), maxs.end());
    }
};

解法二：

动态规划法：

状态转移：将以第 $i$ 个元素开头的子数组的最大和存储在临时变量中，使其不用在下次使用时再计算一遍。

class Solution {
public:
    struct Val{
        bool flag;
        int val;
        Val():flag(false), val(0){};
    };
    int getMaxSum(vector<int>& nums, int i, vector<Val>& tmp){
        if(i == nums.size() - 1) return nums[nums.size()-1];

        if(tmp[i].flag) return tmp[i].val;

        tmp[i].val = std::max(nums[i] + getMaxSum(nums, i+1, tmp),nums[i]);
        tmp[i].flag = true;

        return tmp[i].val;
    }

    int maxSubArray(vector<int>& nums) {
        if(nums.size() == 1) return nums[0];

        vector<Val> maxs(nums.size());
        for(int i = 0; i<nums.size(); ++i){
            nums[i] = getMaxSum(nums,i, maxs);
        }

        return *std::max_element(nums.begin(), nums.end());
    }
};

解法三：

动态规划递推：

思路转变：从后往前，依次求出以元素 nums[i] 的最优解(即以nums[i] 起始的子数组的最大和 tmp , 此值将参与求元素 nums[i-1] 最优解的运算一次。解法如下：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.size() == 1) return nums[0];

        int tmp, maxVal;
        tmp = maxVal = nums[nums.size()-1];

        for(int i = nums.size()-2; i>=0; --i){
            tmp = std::max(nums[i], nums[i] + tmp);
            maxVal = std::max(maxVal, tmp);
        }

        return maxVal;
    }
};

这样该题的时间复杂度为 $O(n)$ . 当然该题的题目里也提示了，可以尝试使用分治法解决该问题，下次再讨论。

LeetCode 上的其他类似题目：

53 Jump Game
152 Maximum Product Subarray
98 House Robber
待补充
注意 152 Maximum Product Subarray 与 98 House Robber 子问题产生了变种，状态可能会改变，但这种改变是可控的。

再一个小结：

对于：可以分解成多个重复的子问题、求最优解 的题目，可以尝试使用动态规划的方法来解题。解决了局部的最优解，即能得到全局的最优解。如果题目比较简单，可以尝试使用直接递推法，否则可以先进行子问题的分解，使用递归的方法解题，再对递归内的状态进行转移，优化成动态规划的解法。

例题 一 : Triangle

解法一：

解法二：

一个小结：

解法三：

解法四：

例题 二：Maximum Subarray

解法一：

解法二：

解法三：

LeetCode 上的其他类似题目：

再一个小结：

例题一 : Triangle

例题二：Maximum Subarray