# [leetcode/lintcode 题解] 阿里面试真题：双色塔

1. 第1层应该包含1块石头，第2层应该包含2块，第i层需要包含i块石头。
2. 同一层的石头应该是同一个颜色（红或绿）。
3. 塔的层数尽可能多。

• red+green≥1
• 0≤red,green≤6×104

样例1

public int twoColorsTower(int red, int green) {
if (red == 0 || green == 0) {
return 1;
}

if (red > green) {
int temp = red;
red = green;
green = temp;
}
// dp[i&1][j]表示前i层一共放j个红石头
int[][] dp = new int[2][red + 1];
dp[1][0] = dp[1][1] = 1;
int level = (int) Math.sqrt(2 * (red + green));
int sum = 1, lower = 0, upper = red;
int curr = 1, prev;
int MOD = (int) 1.0e9 + 7;

for (int i = 2; i <= level; i++) {
sum += i;
int tmpUpper = Math.min(sum, red);
int tmpLower = Math.max(sum - green, 0);
// 红石头不够了，已经是最高层，停止更新
if (tmpLower > tmpUpper) break;
upper = tmpUpper;
lower = tmpLower;
prev = curr;
curr = curr ^ 1;

// j小于本层i，红石只能是之前都放完了
for (int j = lower; j < i; j++) {
dp[curr][j] = dp[prev][j];
}
// 转移方程：dp[i][j] = dp[i-1][j] + dp[i-1][j-i] (when j>=i)
// dp[i-1][j]表示第i层放绿石 dp[i-1][j-i]表示i层放红石
for (int j = i; j <= upper; j++) {
dp[curr][j] = (dp[prev][j] + dp[prev][j - i]) % MOD;
}
}
int ans = 0;
for (int j = lower; j <= upper; j++) {
ans = (ans + dp[curr][j]) % MOD;
}
return ans;
}

+ 订阅