动态规划简介

动态规划思想

1. 算法思想：若要解决一个给定问题，可以先解其子问题，然后根据子问题的解组合出原问题的解；

2. 实质：

找出子问题和原问题的关系——最优子结构；

以及子问题之间的关系——重复子问题。

最优子结构:

• 动态规划要解决的是从解决方案中找到最优解。
• 当我们在求解一个问题时，可以把这个问题分解成多个子问题，然后递归递地找到每个子问题的最优解。
  例：求整数数组的最长递增子序列。——> 子问题拆解：求解以数组中每个元素为结尾的最长递增子序列。——最优子结构。
• 将子问题的解进行组合得到原问题的解是动态规划可行性的关键。
  例：最长子序列问题，如果得到每个元素为结尾的最长递增子序列长度，遍历一遍找出最大值即为整个数组的最长子序列长度。
• 将子问题的解进行组合，我们一般使用状态转移方程描述，得到了状态转移方程我们就可以写出问题的递归实现。
  例：最长子序列问题，列出状态转移方程：

    定义记忆化数组dp[n],使用dp[i]-表示以数组A[i]结尾的最长子序列长度；
    则对dp[i]，若存在0 <= j < i，且A[i] > A[j]，则dp[i] = max(dp[i], dp[j] + 1), 即：
    dp[n] = max{0<= j < i, dp[j] + 1},
    而数组A的最大递增子序列长度 = max(dp[i]);

重复子问题：

• 重复子问题规定的是子问题和子问题间的关系，即：我们在递归求解子问题时，会重复计算更小的子问题。
• 如果递归求解子问题时，没有出现重复子问题，则没必要使用动态规划。
• 解决重复子问题的方法：记忆化递归法，若能事先确定子问题的规模就可以建表存储子问题的答案。

二分法实战笔记

二分法的应用场景

1. 查询固定值在数组中的位置；
2. 求固定值在数组中的上界；
3. 求固定值在数组中的下界；

二分法实现细节

下面以查找固定值在数组中的上界为例，展示代码细节：

int findUpValue(int num, vector<int>& dp)
{
    int left = 0, right = dp.size() - 1;
    while(left <= right) //=号保证数组的左右边界都能遍历到
    {
        int mid = left + (right - left) / 2; //（left + right）/ 2可能导致int类型溢出
        if(dp[mid] == num)
        {
            left = mid + 1;
        }
        else if(dp[mid] > num)
        {
            right = mid - 1;    //应对 num < dp[0]
        }
        else
        {
            left = mid + 1;     //应对 num > dp[dp.size() - 1]
        }
    }
    if(left < dp.size())    //如果求num在数组中的上界，那么当循环退出时，dp[left]不再 <= num
    {                       //如果求num在数组中的下界，那么当循环退出时，dp[right]不再 > num
        return dp[left];
    }
    return -1;  //如果left >= dp.size()，代表数组中没有区间 > num
}