本文主要是介绍【DP】354. 俄罗斯套娃信封问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
法1：DP，LIS问题
基本方法，必须掌握！！！
class Solution {public int maxEnvelopes(int[][] envelopes) {int n = envelopes.length;if (n < 2) {return n;}Arrays.sort(envelopes, (a1, a2) -> {return a1[0] == a2[0] ? a2[1] - a1[1] : a1[0] - a2[0];});List<Integer> list = new ArrayList<>();for (int i = 0; i < n; ++i) {list.add(envelopes[i][1]);}int[] dp = new int[n];int max = 1;Arrays.fill(dp, 1);for (int i = 1; i < n; ++i) {for (int j = 0; j < i; ++j) {if (list.get(i) > list.get(j) && (dp[j] + 1 > dp[i])) {dp[i] = dp[j] + 1;}}max = Math.max(max, dp[i]);}return max;}
}
这篇关于【DP】354. 俄罗斯套娃信封问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
