从动态规划到贪心算法：最长递增子序列问题的方法全解析

主页：17_Kevin-CSDN博客

专栏：《算法》

题型简介

经典例题：300. 最长递增子序列 - 力扣（LeetCode）

最长递增子序列（Longest Increasing subsequence，LIS）是一个经典的问题。最长递增子序列是指在一个序列中，以不下降的顺序连续排列的一系列元素的子序列。这个子序列的长度就是最长递增子序列的长度。

题解代码

虽然注释详细，但与后文解题思路对应食用风味更佳~

#include <iostream>
#include <vector>

using namespace std;

int lengthOfLIS(vector<int>& nums) 
{
    // 如果输入序列为空，返回 0
    if (nums.empty()) 
    {
        return 0;
    }

    // 定义 dp 数组，长度为输入序列的长度
    int dp[nums.size()];
    // 初始化 dp 数组，将所有元素初始化为 1
    for (int i = 0; i < nums.size(); i++) 
    {
        dp[i] = 1;
    }

    // 记录最长递增子序列的长度
    int maxn = 1;

    // 遍历输入序列，从第 2 个元素开始,因为第一个元素的 dp[0] 一定是 1
    for (int i = 1; i < nums.size(); i++) 
    {
        // 遍历之前的元素，找到满足条件的索引 j
        for (int j = 0; j < i; j++) 
        {
            // 如果当前元素小于之前的元素，并且之前元素的最长递增子序列长度加 1 大于当前元素的最长递增子序列长度
            if ((nums[j] < nums[i]) && (dp[j] + 1 > dp[i])) 
            {
                // 更新当前元素的最长递增子序列长度为之前元素的最长递增子序列长度加 1
                // 因为if条件是nums[j] < nums[i]，所以当前i位置的num一定是可以往j位置的数字后拼接作为递增子序列的
                // 所以更新当前i的dp作为新的当前dp[i]
                dp[i] = dp[j] + 1;
            }
        }

        // 在与每次遍历完当前i的j后更新的dp[i]与之前的maxn作对比
        // 得到当前最长递增子序列的长度
        if (dp[i] > maxn) 
        {
            maxn = dp[i];
        }
    }

    // 返回最长递增子序列的长度
    return maxn;
}

int main() 
{
    vector<int> nums = { 10, 9, 2, 5, 3, 7, 101, 18 };
    // 输出：4
    cout << lengthOfLIS(nums) << endl;

    return 0;
}

解题思路

1. 贪心策略（Greedy algorithms）：

贪心算法的核心是以少博多，以最优解为目标。

贪心策略是选择当前未处理元素中最小的元素，将其添加到最长递增子序列的末尾。这种策略的基本思想是尽可能地选择较小的元素，以保证子序列的递增性。

在代码中，我们通过比较当前元素

nums[i]

和之前元素

nums[j]

（

j < i

）的大小来更新最长递增子序列的长度。如果

nums[j] < nums[i]

，并且

dp[j] + 1 > dp[i]

，我们就选择

nums[j]

作为最长递增子序列的一部分，并更新

dp[i]

为

dp[j] + 1

。

2. 动态规划（Dynamic programming）：

动态规划是一种通过将问题分解为子问题来解决问题的方法。在最长递增子序列问题中，动态规划的基本思想是通过递推公式来计算每个元素的最长递增子序列长度。

在代码中，我们使用了一个长度为

nums.size()

的数组

dp

来存储每个元素的最长递增子序列长度。递推公式为

dp[i] = max(dp[j] + 1, dp[i])

，其中

j < i

表示之前的元素。通过递推公式，我们可以逐步计算出每个元素的最长递增子序列长度。

剔骨刀（精细点）

    for (int i = 1; i < nums.size(); i++) 
    {
        for (int j = 0; j < i; j++) 
        {
            if ((nums[j] < nums[i]) && (dp[j] + 1 > dp[i])) 
            {
                dp[i] = dp[j] + 1;
            }
        }

        if (dp[i] > maxn) 
        {
            maxn = dp[i];
        }
    }

动态规划问题难点在于它的递推公式理解。

这里的 (nums[j] < nums[i]) && (dp[j] + 1 > dp[i]) 中的 dp[j] 可以当做前面已经在该下标上取得的最长递增子序列的个数，因为if条件(nums[j] < nums[i]) && (dp[j] + 1 > dp[i])，当条件通过时说明当前 i 位置的num一定是可以往j位置的数字后拼接作为递增子序列的，所以dp[j] + 1的意思就是说，只要在if条件内他都可以拼接，但是如果dp[j] + 1都小于dp[i]的话，那么它就不是最长子序列了，不会进行 +1 ，保留原来的 dp[i] 大小。