解决动态规划问题的思考过程摘录

========================

心得：这里的记忆化颇有意思，dp[i]如果之前计算过，且不为-1，则直接返回dp[i]。如未计算过则计算且只计算一次dp[i]，也就是说，本来递归需要大量重复的计算，却因为之前已经记录了该值而能直接得到结果。给我感觉是提前记录需要重复计算的值，从而提高效率。这种方法配合递归比较细节，着实让人眼前一亮。

摘录：

让我们先从一道例题开始

题目：300.最长上升子序列

描述：

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例：

输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是4。

考虑能否将问题规模减小

将问题规模减小的方式有很多种，一些典型的减小方式是动态规划分类的依据，例如线性，区间，树形等。这里考虑数组上常用的两种思路：

每次减少一半：如果每次将问题规模减少一半，原问题有[10,9,2,5]，和[3,7,101,18]，两个子问题的最优解分别为 [2,5] 和 [3,7,101]，但是找不到好的组合方式将两个子问题最优解组合为原问题最优解 [2,5,7,101]。
每次减少一个：记 f(n) 为以第 nn 个数结尾的最长子序列，每次减少一个，将原问题分为f(n−1), f(n-2), …, f(1)，共 n - 1n−1 个子问题。n - 1 = 7n−1=7 个子问题以及答案如下：

[10, 9, 2, 5, 3, 7, 101] -> [2, 5, 7, 101]
[10, 9, 2, 5, 3, 7] -> [2, 5, 7]
[10, 9, 2, 5, 3] -> [2, 3]
[10, 9, 2, 5] -> [2, 5]
[10, 9, 2] -> [2]
[10, 9] -> [9]
[10] -> [10]

已经有 7 个子问题的最优解之后，可以发现一种组合方式得到原问题的最优解：f(6)的结果 [2,5,7], 7 < 187<18，同时长度也是 f(1)~f(7) 中，结尾小于 18 的结果中最长的。f(7)虽然长度为 4 比 f(6)长，但结尾是不小于 18 的，无法组合成原问题的解。
以上组合方式可以写成一个式子，即状态转移方程

f(n)=maxf(i)+1 其中 i<n 且 a[i]<a[n]

这种思考如何通过f(1)…f(n-1)求出 f(n)的过程实际就是在思考状态转移方程怎么写。

总结：解决动态规划问题最难的地方有两点：

如何定义 f(n)
如何通过 f(1), f(2), … f(n−1) 推导出f(n)，即状态转移方程

1. 递归

有了状态转移方程，实际上已经可以直接用递归进行实现了。

int f(vector<int>& nums, int i)
{
    int a = 1;
    for(int j = 0; j < i; ++j)
    {
        if(nums[j] < nums[i])
        ¦   a = max(a, f(nums, j) + 1);
    }
    return a;
}

2. 自顶向下（记忆化）

递归的解法需要非常多的重复计算，如果有一种办法能避免这些重复计算，可以节省大量计算时间。记忆化就是基于这个思路的算法。在递归地求解子问题 f(1)f(1), f(2)f(2)… 过程中，将结果保存到一个表里，在后续求解子问题中如果遇到求过结果的子问题，直接查表去得到答案而不计算。

int f(vector<int>& nums, int i, vector<int>& dp)
{
    if(dp[i] != -1) return dp[i];
    int a = 1;
    for(int j = 0; j < i; ++j)
    {
        if(nums[j] < nums[i])
        ¦   a = max(a, f(nums, j) + 1);
    }
    dp[i] = a;
    return dp[i];
}