动态规划算法（一）

概述

本篇回忆了动态规划问题的基本特征和求解的基本套路。
简单分析了问题走台阶问题和最大连续子数组问题

什么是动态规划？(dynamic programing)

动态规划是一种算法思想，其命名的两个单词，dynamic和programing揭示了这种算法的思想特征，即为了求解问题需要不断在局部的子问题中求解最优值。
例如，一个比较简单的经典例子：
求解斐波那契数列的第n项。

我们知道, 斐波那契数列的定义：

image.png

除了开头的两项，每一项的值都依赖前两项的值。子问题f(n-2)和f(n-1)的解又依赖其它子问题的解, 这个递推过程不断膨胀，会得到一颗增长非常庞大的子问题树。如果递归求解，效率是非常慢的。为了优化速度，可以建立一个表来记忆已经计算过的中间结果，可以使用O(n)的时间复杂度和O(1)的空间复杂度求得问题的解。

子问题树，f(8)、f(7)... 被反复求解

动态规划 当我们要求解一个问题，可以将问题拆解成若干个子问题，并且可以根据子问题的结果计算出最终问题的解，那么该问题就具备了动态规划求解的可能。我们知道分治的策略与此过程类似，二者的主要区别是：

• 分治策略中，子问题之间是被分割的，彼此之间不依赖；而动态规划问题中，子问题一般相互重叠
• 动态规划问题的子问题具有最优子结构，即，最终解蕴含在子问题的最优解中。

以上斐波那契数列的例子中， 为了求解 f(n), 我们根据递推式，得到了它的两个子问题 f(n-1) 和 f(n-2)， 子问题的解求出之后，可以直接得到最终问题的解。它就具备了动态规划求解的特征。

实际问题中，我们通常没有那么直观的递推式。

走台阶问题

比如斐波那契数列求解有一个不那么直观的登台阶的问题：
假设有一个台阶，共有n级，小明每次可以向上走1步或2步，问：小明共有多少种走法登上顶。
令 T(n) 是登上第n级台阶的走法
当台阶只有 1 级时，显然小明只能走一步上去 T(1) = 1;
当台阶只有 2 级时，小明可以走两次1步登上去，也可以一次登2步， 因此 T(2) = 2
当 n = 3时， 小明可能的走法 1 + 1 + 1 = 3, 或1 + 2 = 3 或 2 + 1 = 3 因此 T(3) = 3

我们可以运用动态规划的思路
考察T(n)的子问题 T(n-1)
假设我们已经求得T(n-1), 那么小明抵达n - 1级后，只需要再向前迈一步就到达第n级。
另外到达第n级并不是必须要经过第n-1级，因为可以一次走2步，所以不经过第n-1级到达n级的走法必须经过第n-2级。
此外我们还可以稍微论证一下，所有到达第n级的走法要么经过第n-1级，要么不经过第 n-1 级，不经过第n-1级的走法必须经过第n-2级。
因此关于 T(n)我们得到一个基本的子问题的拆分:
一种是必须经过第n-1级的走法，它的数量是 T(n-1)
另一种是不经过第n-1级的走法，此时必须经过第n-2级，然后再迈一次两步可到达第n级。写成递推式则是

T(n) = T(n-1) + T(n-2), n ≥ 3
T(1) = 1, n = 1
T(2) = 2, n = 2

伪代码

calc_step_cnt(n):
  if n == 1
     return 1
  if n == 2
     return 2
  let a = 1, b = 2
  for i in range[3, n]
       a, b = b, a + b
  return b

最大连续子数组问题

假设一个整数数组 An，它包含 下标为0，1, ... , n - 1的n个整数，其中有正数和负数，计算它最大的连续子数组的和是多少？
朴素的想法是，将数组的所有连续子数组的和计算出来，由于连续子数组的起始下标分别可以是从0 到 n - 1, 最后求最大值需要一次复杂度为O(n)的计算，暴力解法的时间复杂度将会达到O(n³).
经过一些技巧优化，可以将复杂度降到 O(n²）

另外一种分治解法可以将时间复杂度优化到O(n logn)。即我们考虑将数组从中间分成两半 A[0, n/2], A[n/2, n],
那么最大连续子数组有三种情况：

• 1 在左半子数组上
• 2 在右半子数组上
• 3 跨越分界点

对于1和2的情形， 处理起来相对简单。重点关注第3种情形。由于子数组被固定，并需要穿过数组的中点，那么我们可以计算所有跨过中点的连续子数组的和，取最大的那个，这个过程只需要O(n)的时间。分治拆分时间复杂度是log(n)，整个算法的复杂度为O(nlogn)

int  max_subarray(int nums[], int l, int r)
{
        if (l >= r) {
            return nums[l];
        }
        int mid = l + (r - l) / 2;
        int max_crossmid = nums[mid];  //max_crossmid记录跨越中点的最大连续子数组的和
        int sum = 0;
        for (int i = mid; i >= l; --i) {
            sum += nums[i];
            max_crossmid = max(max_crossmid, sum);
        }
        sum = max_crossmid; 
        for (int i = mid + 1; i <= r; ++i) {
            sum += nums[i];
            max_crossmid = max(max_crossmid, sum);
        }
        return max(max(max_subarray(nums, l, mid), max_subarray(nums, mid + 1, r)), max_crossmid);
    }

分治算法对子问题的拆分：左半数组和右半数组互不关联，问题不重叠，可以通过递归逐渐求解。

考虑另一个子问题划分策略：我们用 S(n）表示数组A[0,n]中以第n项A[n]结尾的最大连续子数组的和。
那么考察其子问题 S(n-1)

如果 S(n - 1) < 0, 那么为了求得最大和，对于S(n)而言，可以抛弃前面的负值只留下 A[n]项，因此S(n) = A[n];
如果S(n - 1) ≥ 0, 那么很显然， S(n) = A[n] + S(n-1)。
数组的最大连续子数组的和最终是 max{S(i)} ，i = 1, 2, ..., n
写成表达式：

image.png

算法实现：

int maxSubArray(vector<int>& nums) {
        if (nums.size() == 0) {
            return 0;
        }
        vector<int> s(nums.size());
        s[0] = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            if (s[i - 1] < 0) {
                s[i] = nums[i];
            } else {
                s[i] = s[i - 1] + nums[i];
            }
        }
        return *max_element(s.begin(), s.end());
    }

以上算法可以进一步优化，在循环体内顺带维护S(n)序列的最大值, 只需要维护当前以A[i]为右界的连续数组的最大和，以及所有右界产生的这个和的最大值就可以，因此无须用一个数组的额外空间，简化为两个变量。
以下是这种简化之后的代码，惊奇的是，这个算法只需要一次循环就实现了，因而时间复杂度是O(n)。
如果你甫一看这段代码，很难将上面的动态规划的分析思路联系起来。

int maxSubArray(vector<int>& nums) {
        if (nums.size() == 0) {
            return 0;
        }
        int max_rightbound_sum = 0; // 表示以A[i]为右界的连续子数组的最大和
        int max_sum = nums[0]; //表示每个元素对应的sum中最大的数
        for (int i = 0; i < nums.size(); ++i) {
            if (max_rightbound_sum < 0) {
                max_rightbound_sum = nums[i];
            } else {
                max_rightbound_sum += nums[i];
            }
            if (max_sum < max_rightbound_sum)
                max_sum = max_rightbound_sum;
        }
        return max_sum;