354. 俄罗斯套娃信封问题题解

废话不说 先上代码：

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        if(envelopes.length<=1){
            return envelopes.length;//如果小于等于1直接返回数组长度
        }
        int dp[]=new int[envelopes.length];
        for(int i=0;i<envelopes.length;i++){
            dp[i]=1;//初始化DP数组，一般初始值时指最快情况下的值。
        }
        int res=1;

        Arrays.sort(envelopes,(a,b)->a[0]==b[0]?b[1]-a[1]:a[0]-b[0]);//先把envelopes按字段0升序，然后把字段1升序
        for(int i=0;i<envelopes.length;i++){//确保能被第i个套上的都在第i个前面
            for(int j=0;j<i;j++){//单串MAX前O(n)个情况
                if(envelopes[j][0]<envelopes[i][0] && envelopes[j][1]<envelopes[i][1]){
                    dp[i]=Math.max(dp[i],dp[j]+1);//获得更优解 更新 这里的更新函数是max
                }
            }
            res=Math.max(dp[i],res);//刷新最优解的值
        }
        return res;//返回最终结果
    }

}

核心思路 看到一个二维数组进来先不要急着是二维DP
进来的如果是一个地图让你求路径的，或者求最大正方形的是二维无疑，这种一般是MN,对于所有的测试数据来说，M和N的值都是不固定地。当然不排除一种可以把二维压缩 为一维的DP
像这种MX的,对于所有测试数据X的值是固定的（一般是2），比如输入data[M][2] 那么他很有可能是可以先把输入的data[i]按data[i][0]排序，然后直接LIS处理
这种题目的特点就是每一个个体/对象，比如球员，信封，小朋友等等有多个但数量固定的属性，在java中可以用List<object>表示的。有的可能用双蹿来输入 注意。</object>