讨论/《动态规划精讲(一)》 - 俄罗斯套娃信封问题/
《动态规划精讲(一)》 - 俄罗斯套娃信封问题
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0]>o2[0]){
                    return 1;
                }else if(o1[0]<o2[0]){
                    return -1;
                }else if(o1[1]>o2[1]){
                    return 1;
                }else if(o1[1]<o2[1]){
                    return -1;
                }else{
                    return 0;
                }
            }
        });
        if(envelopes.length==1) return 1;
        int[] dp=new int[envelopes.length];
        Arrays.fill(dp,1);
        int maxans=1;
        for(int i=1;i<envelopes.length;i++){
            for(int j=0;j<i;j++){
                if(envelopes[i][0]>envelopes[j][0] && envelopes[i][1]>envelopes[j][1]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
            maxans=Math.max(maxans,dp[i]);
        }
        return maxans;
    }
}
展开全部 12 讨论