力扣2771题详解：动态规划解最长非递减子数组问题

一、问题描述

给定两个长度相同的数组nums1和nums2，我们需要构造一个新数组nums3，其中每个元素可以选择来自nums1或nums2对应位置的元素。要求找到nums3中最长的非递减子数组的长度。

二、解题思路

这道题可以采用动态规划高效解决：

1. 定义两个dp数组分别记录选择nums1和nums2时的最长长度

2. 通过状态转移方程考虑所有可能的转移情况

3. 在遍历过程中维护全局最大值

三、完整代码解析

class Solution {
public:
    int maxNonDecreasingLength(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        if (n == 0) return 0;
        
        // dp1[i]表示选择nums1[i]时的最长非递减子数组长度
        // dp2[i]表示选择nums2[i]时的最长非递减子数组长度
        vector<int> dp1(n, 1), dp2(n, 1);
        int max_len = 1;
        
        for (int i = 1; i < n; ++i) {
            // 当前选择nums1[i]的情况
            if (nums1[i] >= nums1[i-1]) {
                dp1[i] = max(dp1[i], dp1[i-1] + 1);
            }
            if (nums1[i] >= nums2[i-1]) {
                dp1[i] = max(dp1[i], dp2[i-1] + 1);
            }
            
            // 当前选择nums2[i]的情况
            if (nums2[i] >= nums1[i-1]) {
                dp2[i] = max(dp2[i], dp1[i-1] + 1);
            }
            if (nums2[i] >= nums2[i-1]) {
                dp2[i] = max(dp2[i], dp2[i-1] + 1);
            }
            
            // 更新全局最大值
            max_len = max(max_len, max(dp1[i], dp2[i]));
        }
        
        return max_len;
    }
};

四、关键点解析

1. DP数组定义：使用两个dp数组分别处理选择不同数组的情况

2. 状态转移：考虑四种可能的转移情况（nums1→nums1, nums2→nums1, nums1→nums2, nums2→nums2）

3. 初始化：每个位置初始长度为1

4. 边界处理：空数组直接返回0

五、实际应用

这种动态规划技巧在解决序列相关问题时非常高效，类似的题目包括：

• 最长递增子序列

• 最长公共子序列

• 最大子数组和等

六、总结

通过这道题，我们学习了：

1. 如何定义多个dp状态处理选择问题

2. 状态转移方程的构建技巧

3. 动态规划在序列问题中的应用

4. 时间复杂度优化思路