有很多个尺寸不一的红包,以数组的形式给出,其中redPockets[i]= [w, h],表示这个红包的宽度和长度。 当—个红包的宽度和长度比另一个红包大时,就可以将小的红包放入大的红包之中,组成一个套娃红包。 请计算出在给出的红包中,最多能用多少个红包组合成一个套娃红包。用Java实现
时间: 2023-03-25 10:02:17 浏览: 150
我可以回答这个问题。可以使用动态规划来解决这个问题。首先,将红包按照宽度从小到大排序,如果宽度相同,则按照长度从小到大排序。然后,定义一个数组dp,其中dp[i]表示以第i个红包为最外层红包时,最多能组成的套娃红包个数。初始时,dp数组的所有元素都为1。接下来,从第二个红包开始遍历,对于每个红包i,遍历它之前的所有红包j,如果红包i可以放入红包j中,即redPockets[i][]<redPockets[j][]且redPockets[i][1]<redPockets[j][1],则更新dp[i]的值为dp[j]+1。最后,遍历dp数组,找到最大值即为最多能组成的套娃红包个数。
以下是Java代码实现:
public int maxEnvelopes(int[][] envelopes) {
if (envelopes == null || envelopes.length == ) {
return ;
}
Arrays.sort(envelopes, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
if (a[] == b[]) {
return a[1] - b[1];
} else {
return a[] - b[];
}
}
});
int n = envelopes.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
int max = 1;
for (int i = 1; i < n; i++) {
for (int j = ; j < i; j++) {
if (envelopes[i][] > envelopes[j][] && envelopes[i][1] > envelopes[j][1]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
max = Math.max(max, dp[i]);
}
return max;
}
阅读全文