HJ103 Redraiment 的走法：最长递增子序列求解

HJ103 Redraiment 的走法

题目描述

Redraiment 是走梅花桩的高手。现在，地上有 n 个梅花桩排成一排，从前到后高度依次为 h1, h2, ..., hn。 Redraiment 可以任选一个梅花桩开始，向后跳到任意一个比当前高度高的梅花桩上。 求 Redraiment 最多可以跳过多少个梅花桩。

输入描述

第一行输入一个整数 n (1≤n≤200) 代表梅花桩的数量。 第二行输入 n 个整数 h1, h2, ..., hn (1≤hi≤350) 代表每一个梅花桩的高度。

输出描述

输出一个正整数，代表 Redraiment 最多可以跳过多少个梅花桩。

示例

输入： 6 2 5 1 5 4 5

输出： 3

说明： 在这个样例中，其中一个最优的选择是，从第一个桩子起跳，最多可以跳三个梅花桩。另外一种最优选择是，从第三个桩子起跳，最多也可以跳三个梅花桩。

方法一：暴力枚举

使用二进制进位法遍历所有可能组合，再挑选出符合题意的最长子序列。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int GetRes(const vector<int> nums) {
    int max_len = 0;
    int n = nums.size();
    if (n <= 1) {
        return n;
    }
    // i 表示起点
    for (unsigned long long int mask = 0; mask < (1 << n); ++mask) {
        vector<int> tmp;
        // j 表示后边需要跳入位置的起点
        for (int j = 0; j < n; ++j) {
            if (mask & (1 << j)) {
                tmp.push_back(nums[j]);
            }
        }
        bool flag = true;
        int cnt = 0;
        for (int j = 0; j < (int)tmp.size() - 1; ++j) {
            if (tmp[j] > tmp[j + 1]) {
                flag = false;
                break;
            }
            cnt++;
        }
        if (flag && max_len < (int)tmp.size()) {
            max_len = tmp.size();
        }
    }
    return max_len;
}

int main() {
    int n = 0;
    while (cin >> n) {
        vector<int> nums(n, 0);
        for (int i = 0; i < n; ++i) {
            cin >> nums[i];
        }
        cout << GetRes(nums) << endl;
    }
    return 0;
}

该方法在 OJ 上运行可能会超时，但本地运行正常。

方法二：逆向动态规划

核心思想

1. 逆向动态规划：从数组末尾开始向前遍历，计算以每个元素 nums[i] 开头的最长递增子序列长度。
2. 状态转移：对于当前元素 nums[i]，检查其后所有比它大的元素 nums[j]，选择其中 dp[j] 最大的值，然后加 1（包含自身）。
3. 结果提取：最终遍历 dp 数组，找到最大值即为整个数组的最长递增子序列长度。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int GetRes(const vector<int> nums) {
    int n = nums.size();
    vector<int> dp(n, 0);
    // 每个点开始的最长升序长度，表示以 `nums[i]` 开头的最长递增子序列的长度
    dp[n - 1] = 1;
    // 最末端开始的序列只有它自身，长度为 1
    // 逆向动态规划填充 `dp` 数组
    // 从后向前计算每个点的 dp[i],从倒数第二个数开始往前遍历，因为倒数第一个数已经初始化为 1
    for (int i = n - 2; i >= 0; --i) {
        // 检查 i 之后的所有元素，先继承数值比 i 大的数据中递增序列最长的长度，然后再包含自身，自增 1
        for (int j = i + 1; j < n; ++j) {
            if (nums[i] < nums[j] && dp[j] > dp[i]) {
                // 记录后继节点的个数，这里 dp 是递减数组，dp[j] 一定大于后边的数值，所以只会进来一次
                dp[i] = dp[j];
            }
        }
        dp[i]++; // 包含自身长度
    }
    int max_len = 0;
    for (int i = 0; i < n; ++i) {
        max_len = (dp[i] > max_len) ? dp[i] : max_len;
    }
    return max_len;
}

int main() {
     n = ;
     (cin >> n) {
        ;
         ( i = ; i < n; ++i) {
            cin >> nums[i];
        }
        cout << (nums) << endl;
    }
     ;
}

方法三：动态规划

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int GetRes(const vector<int> nums) {
    int n = nums.size();
    // dp[i] 的含义是以第 i 个桩子结尾走的最多的步数，初始化为 1 表示包含自身
    vector<int> dp(n, 1);
    int res = 0;
    // 从第 1 个位置开始计算
    for (int i = 1; i < n; ++i) {
        // 遍历 i 位置之前的所有元素
        for (int j = 0; j < i; ++j) {
            // 如果 i 元素之前有元素值更小的元素 j，且 i 当前的步数小于 dp[j] + 1 才更新 i 当前的步数
            if (nums[j] < nums[i] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
            }
        }
        res = (res < dp[i]) ? dp[i] : res;
    }
    return res;
}

int main() {
    int n = 0;
    while (cin >> n) {
        vector<int> nums(n, );
         ( i = ; i < n; ++i) {
            cin >> nums[i];
        }
        cout << (nums) << endl;
    }
     ;
}

方法四：贪心 + 二分查找

核心思想

1. 贪心策略：维护一个数组 dp，其中 dp[i] 表示长度为 i 的递增子序列的最小末尾元素。
2. 二分优化：通过二分查找快速定位当前元素 nums[i] 在 dp 数组中的插入位置，保证 dp 数组始终有序。
3. 动态更新：
   • 若 nums[i] 大于 dp 的最后一个元素，直接扩展序列长度。
   • 否则，用 nums[i] 替换 dp 中第一个大于或等于它的元素，以维持最小末尾性质。

为什么需要保持最小末尾性质？

在求解最长递增子序列（LIS）时，保持最小末尾性质的核心目的是为了最大化后续扩展的可能性。 具体来说：

1. 贪心策略的核心思想：我们希望让递增子序列的末尾元素尽可能小，这样后续遇到更大的数时，更容易扩展序列长度。
2. 例子：假设当前有两个长度为 3 的递增子序列：[5, 1, 3]，初始化 dp[1] = 5，很明显最长子序列为 [1, 3]，如果不将 dp[1] = 5 替换成 dp[1] = 1，后边将无法扩展。

为什么需要插入（替换）操作？

假如后边某个数据是最小的则替换最前面的，但并没有影响结果，因为 nums[i] 的遍历顺序不会改变，还是会基于 len 的基础上继续扩展。

关键结论

1. 最小末尾性质：保证 dp 数组的每个 dp[i] 是长度为 i 的子序列的最小末尾，从而最大化扩展机会。
2. 替换操作：通过替换 dp 中的较大值为更小的 nums[i]，确保不遗漏任何可能的扩展。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

// 二分查找
int binSearch(int v, vector<int> & dp, int len) {
    int left = 1, right = len, mid;
    while (left <= right) {
        mid = (right + left) / 2;
        if (dp[mid] >= v) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

int GetRes(const vector<int> nums) {
    int n = nums.size();
    vector<int> dp(n + 1, 0);
    // dp[i] 的含义是长度为 i 的序列最小的结尾数字
    int len = 1; // 最大步数
    // 初始时，长度为 1 的子序列就是第一个元素本身。
    dp[len] = nums[0];
    for (int i = 1; i < n; ++i) {
        // 如果有更长的序列则设置 len++ 步长的是为元素 nums[i]，即当前元素大于 dp 末尾，直接扩展
         (nums[i] > dp[len]) {
            len++;
            dp[len] = nums[i];
        }   (nums[i] < dp[len]) {
            
            
            
             pos = (nums[i], dp, len);
            dp[pos] = nums[i];
        }  {
            
        }
    }
     len;
}

{
     n = ;
     (cin >> n) {
        ;
         ( i = ; i < n; ++i) {
            cin >> nums[i];
        }
        cout << (nums) << endl;
    }
     ;
}