LC-2771. 构造最长非递减子数组（记忆化dfs的自我解惑）

写在前面

感觉这道题很适合记录一下，打破了我对 $dfs$ 的思维范式~

2771. 构造最长非递减子数组

想不通的点

递归的传参怎样设置？
递归的 $base$ $case$ 怎么写？
如何进入下一个递归，递归入口在哪？
在 $dfs$ 的过程中，如果中间值不满足非递减特性了怎么办？最终返回的答案应该是什么？
如何设置 $memo$ 数组？

记忆化 dfs

为了更加容易 $1:1$ 改写成 $DP$, 这里递推写成从后往前的。

思考1：递归应该传入哪些参数？
- 除去必要的数组信息：$num1$, $nums2$
- 题目要求的是以索引 $i$ 结尾的最长递减子序列，$dfs$ 函数自然需要这样一个参数，从而可以从 $i-1$ 的位置转移到 $i$ 的位置；另外，需要知道 $i$ 位置选择了什么数据（来自$nums1$ 还是 $nums2$）；这里也是 $memo$ 写法的重要思考依据。
思考2：递归的 $base$ $case$ 应该怎么写？
- 因为是从右往左遍历的，因此左边界，就是 $i==0$ 的情况，因为一个数也是一个子数组，长度为 $1$，因此应该返回 $1$。
思考3：如何进入下一个递归入口？
- 根据题意判断入口，也就是可以分解成子问题的入口~
- 因为 $i-1$ 可以选择的数有两个，可以来自 $nums1$，也可以来自 $nums2$，因此应该分情况讨论：
  - 如果不存在比 $i$ 位置选择的数，也就是找不到满足非递减特性的数字了，应该返回多少？（应该返回1，而不是零，因为其本身可以作为一个子数组）
  - 如果 $nums1$ 满足，可以选择，怎么写递归？
  - 如果 $nums2$ 也满足，可以选择，应该怎么写递归？
  - 最后的返回值如何确定？（取三个可能中的最大值）
```
int dfs(vector<int>& nums1, vector<int>& nums2,int i,int it,vector<vector<int>>& memo){
if(i==0)
return 1;
int res=1;
if(memo[it][i]!=-1)
return memo[it][i];
if(nums1[i-1]<= (it==0 ? nums1[i] : nums2[i]))
res=dfs(nums1,nums2,i-1,0,memo)+1;
if(nums2[i-1]<= (it==1 ? nums2[i] : nums1[i]))
res=max(res,dfs(nums1,nums2,i-1,1,memo)+1);
memo[it][i]=res;
return res;
}
```
思考4：在 $dfs$ 的过程中，如果中间值不满足非递减特性了怎么办？最终返回的答案应该是什么？
- 一般的 $dfs$ 都是直接计算出 $dfs(i)$ 即可得出最终结果
- 但是，这里可以前面半段的满足，后半段满足，这样应该怎么考虑？也就是可能是中间位置的组合数作为末尾得到的最长，呢么自然就能想到：
  - 枚举所有可能：因为最长非递减子数组是整体组合数组的一部分，每一个组合元素都有可能是作为最长非递减子数字的末尾
- 最终的返回答案：每一个位置都可能作为最长非递减子数组的末尾，而且每个位置有两种选择。
思考5：如何设置 $memo$ 数组？
- 很明显，我们需要枚举每个位置，同时需要递归，很显然有很多重叠子问题（或者说状态位置）
- 思考有哪些状态位置：对于每个位置，每个位置有两种状态（也就是选择了哪个数组里的数），因此可以考虑使用两行 $m$ 列来存储 $memo$，总共也就这么多状态。
- 这里和传入参数的写法是联动的，在上述代码中，使用 $int=0或1$ 来代表选择的数组数，这样 $memo$ 数组也就很明晰了。

总结一下🌏

$dfs$ 的传入参数往往是和状态位置相关的，而且一般来说都是从后往前思考，这样也方便翻译成 DP
注意枚举的使用，有的时候就是要枚举的
- 例如对应的周赛 2767. 将字符串分割为最少的美丽子字符串, 枚举递归入口
- 本题中的返回结果，也就需要枚举所有可能。
不一定 $dfs(末尾状态 i)$ 就是返回结果，本题中每个状态都有可能是返回结果。不要陷入思维定式！！
$memo$ 数组的设计和状态的定义密切相关，本题中就是索引位置及对应选择的数。索引位置有 $m$ 个，每个位置都有两种可能（避免使用值来作为传入参数，传入 $flag$ 反而简单明晰）。

贴个代码吧

就不 $1:1$ 翻译成递推了~

class Solution {
public:
    int maxNonDecreasingLength(vector<int>& nums1, vector<int>& nums2) {
        int m=nums1.size();
        int res=0;
        vector<vector<int>> memo(2,vector<int>(m,-1));
        // 枚举所有位置的可能
        for(int i=0;i<m;i++){
            // 每个位置又包含两种可能
            int res1=dfs(nums1,nums2,i,0,memo);
            int res2=dfs(nums1,nums2,i,1,memo);
            // 最终返回值是这些中的最大值
            res=max({res,res1,res2});
        }
        return res;
    }
    // dfs(i) 表示以 nums[i] 结尾的最长非递减数组的长度，传入参数有两个，位置以及选择的数来自谁
    int dfs(vector<int>& nums1, vector<int>& nums2,int i,int it,vector<vector<int>>& memo){
        if(i==0)
            return 1;  
        // 传入的状态参数也对应着memo的维度
        if(memo[it][i]!=-1)
            return memo[it][i];
        // 枚举递归入口
        int res=1;  
        if(nums1[i-1]<= (it==0 ? nums1[i] : nums2[i]))
            res=dfs(nums1,nums2,i-1,0,memo)+1;
        if(nums2[i-1]<= (it==1 ? nums2[i] : nums1[i]))
            res=max(res,dfs(nums1,nums2,i-1,1,memo)+1);
        memo[it][i]=res;
        return res;
    }
};

$\cdots$ 什么都略懂一点，生活更多彩一些 $\cdots$

$\cdots$ end $\cdots$