动态规划算法(二)

在上一篇中 动态规划算法（一)
由几个经典问题：斐波那契数列，登台阶问题以及最大连续子数组问题，对动态规划有了一个基本的认知。
动态规划大约由数学家理查德·贝尔曼在40年代发明，在数学，管理科学，计算机科学，经济学，和生物信息学都有运用。一般用于解决具有最优子问题结果，并且子问题具有重叠特性的问题。

动态规划一般的设计方法如下：

• 刻画出一个最优解的结构特征。对于斐波那契数列递推式，它的结构特征即蕴含在它的递推式中；对于最大连续子数组问题，它的结构特征则是需要适当的构造，我们构造了一组特征数：以每个成员为右界的最大连续子数组的和。

• 递归定义最优解的值 ，几乎大多数动态规划问题都能转化为数学公式的形式，左边是待求解的F(n), 右边可能是由若干子问题表达的式子。有时候不是问题直接的拆解，而是转换为关联的问题，然后最优解依赖这个关联的问题。

• 计算最优解 这一步一般是根据递归定义的递推式对子问题逐步求解的过程（有时候也被人称为状态转移方程）

• 构建最终的最优解 在最大连续子数组问题中，即求第一步构造的特征数的最大值。

最长上升子序列

给定一个数组A[0,n]，假设全部由整数构成，求这个数组中最长单调上升的子序列的长度。

例如：
数组 [10,1,9,2,2,3,7,101,18] 它的最长递增的子序列是 [1,2,3,7,18], 结果为5

动态规划求解问题最困难的部分在于第一步和第二步：如何刻画它的问题结构特征，从而建立状态转移方程，也就是递推式。

对于这个问题，我们仍然沿用最大子序列问题中的技巧，构造一个以数组中每个元素作为右界的上升子序列的最长长度的特征数组 R[0,n] , R[i] 表示以元素A[i], 0 ≤ i < n为右界的上升子序列的最长长度。

显然，对任意的 0 ≤ i < n, R[i] ≥ 1;
考察 R[i + 1], 如果A[i+1] > A[i], 显然我们可以将A[i+1]加入到子序列中，将上升子序列的长度扩充1,所以 我们得到R[i+1]的一个下界：

R[i + 1] ≥ R[i] + 1

实际上，对所有小于 0 ≤ j < i + 1的j，只要 A[j] < A[i+1] 都可以得到 类似上面的不等式，

R[i + 1] ≥ R[j] + 1,   0 ≤ j < i + 1 且 A[j] < A[i+1]

因为A[j] ≥ A[i+1], A[j]无法加到R[j]的最右边，这时R[i+1]的一个上界可以在A[0,i]中找出那些小于A[i+1]的数对应的最大的R[j], 0 ≤ j < i + 1
即：

递推式

简单论证一下上面的递推式， 对每个 0 ≤ j < i + 1 且 A[j] < A[i+1] 上面已经论证了 R[j] + 1 是R[i+1]的一个下界。R[ i+1] 必须包含A[i+1]， 所以那些比A[i+1]大的j ( 0 ≤ j < i + 1), 无法加入A[i+1]，所以R[i+1]必在小于A[i+1]的那些R[j]中取，然后拼接A[i+1]。

以上的递推式（状态转移方程）可以逐步计算出所有的R[i] 0 ≤ i < n, 最终我们合成的解就是
max {R[i]} (0≤ i < n)

int length_of_LIS(vector<int>& nums) {
        auto n = nums.size();
        vector<int> R(n);
        R[0] = 1;
        for (auto i = 0; i < n; ++i) {
            int max_r = 1;
            for (auto j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) {
                    if (max_r < R[j] + 1)
                        max_r = R[j] +1;
                }
            }
            R[i] = max_r;
        }
        return *max_element(R.begin(), R.end());
    }

这个算法的时间复杂度是O(n²) 因为，每次寻找最大的R[i]时，需要一个O(n)的时间来查到最大值，能否优化这个过程？

偷窃问题

一个小偷去一个村庄偷东西，假设他不能同时偷相邻的房屋，否则会触发报警系统，已知每个房屋可以偷取的价值，求最优偷窃方案。用数组array[n]表示每个房屋可偷取的最大价值。

例如，[5,2,3]可以选择偷第1和第3户，得到最大的总价值为8；
[1,100,3] 选择偷第2户，得到的总价值为100；
[1,100,1,3,18] 选择第2和第5户，得到总价值为118。

暴力解法的思路：计算所有可能的组合：
考虑一个有10个房屋的序列，我们有两种方法开始偷窃之旅，从第1间开始，从第2间开始。
不能从第三间开始：因为价值序列是正整数，这时可以顺带偷窃第1间，将偷窃价值增加。

每次偷完一间房屋，都有两个选择继续下去，要么隔1间，要么隔2间

子问题树

最终我们画出两棵树（方便起见，上图省略了开始的空节点，实际上可以整合成一棵树）每个叶子节点对应一种偷窃路径。
如果沿着每种路径求和一次，我们会发现实际上会重复求解，例如图中的蓝色子树，实际上是一样的。唯一的区别就是它是从1出发还是从2出发。穷举法会导致重复问题求解，编码中体现为反复对同一组数求和。

使用动态规划的思路求解。
首先我们要提取一个最优解的特征，构造子问题：用dp[i]表示偷窃路径必经第i个房屋的偷窃最大值。

dp[i]有两种方式构成，一种是经过第i-2个房屋，此时dp[i-2]再加上array[i]就是dp[i];另一种是不经过第i-2间房子，那么，因为每次偷窃只能隔1间或2间房子，那么不经过第i - 2的偷法必然经过第 i - 3间房子，这种路径的最大值可以考虑从dp[i-1] 中减去array[i-1]然后补上array[i]得到，因而得到子问题一个递推式：

dp[0] = array[0] ;
dp[1] = max(array[0], array[1]}
dp[i] = max{dp[i-2] + array[i], dp[i-1] + array[i] - array[i-1]} i ≥ 2

重构最优解
注意到，最优偷窃选择要么最后经过的房子是最后一间，要么是倒数第二间，不可能最后两间屋子都不经过，为什么？（不管不经过n-1, n-2的偷法有没有经过n-3，我们总是可以选择n-1或n-2使总价值增加）

所以最终的解:
max_rob = max(dp[n-1], dp[n-2])

int rob(vector<int>& nums) {
        if (nums.size() == 1) {
            return nums[0];
        }
        if (nums.size() == 2) {
            return max(nums[0], nums[1]);
        }
        
        int dp0 = nums[0], dp1 = nums[1];
        for (auto i = 2; i < nums.size(); ++i) {
            int tmp = dp1;
            dp1 = max(nums[i] + dp0, nums[i] - nums[i-1] + dp1);
            dp0 = tmp;
        }
        return max(dp0, dp1);
    }

每个阶段的最优解只依赖前两个问题的最优解，因此只需要维持两个变量不断迭代即可，最终算法的时间复杂度是O(n),空间复杂度是O(1)