Smart喜欢玩骨牌。一天，他沿着一条直线放了 n 颗骨牌，从左往右坐标依次为x1,x2,xn, 每颗骨牌都有它的高度，第i个骨牌的高度为hi Smart 可以放倒一颗骨牌，然后把它倒向左边，那它就占据了区间[xi-hi,xi]; 或者把它倒向右边， 那它就占据了区间[xi,xi+hi] ，没有被放倒的骨牌只占据一个坐标为xi的点。 现在的问题是他最多能放倒多少个骨牌，使得任意两个骨牌，彼此之间占据的部分都没有公共部分。

可以使用贪心的思想来解决这个问题。首先将所有骨牌按照右端点坐标从小到大排序。然后从左往右遍历每一个骨牌，对于每一个骨牌，如果它的左端点和右端点都没有被其他骨牌占据，那么它就可以被放倒。否则，就不放倒这个骨牌。

具体实现时，可以用一个数组记录每个坐标上的骨牌数量，初始值都为1，表示该位置上有一个未被放倒的骨牌。然后按照右端点从小到大排序，对于每一个骨牌，从它的左端点到右端点遍历一遍，将这些位置上的骨牌数量减一，表示它们已经被占据了。如果在遍历过程中发现某个位置上的骨牌数量已经为0了，说明这个位置上已经有其他骨牌占据了，那么就不放倒当前的骨牌。如果遍历完整个区间都没有发现任何位置上的骨牌数量为0，那么就放倒当前的骨牌，并将它占据的位置上的骨牌数量设为2，表示这个位置上已经有两个骨牌占据了。

最后统计一下被放倒的骨牌数量即可。时间复杂度为O(nlogn)，因为需要对所有骨牌按照右端点排序。

相关问题

有 2*n 的一个长方形方格，用一个 1 * 2 的骨牌铺满方格

题目描述：在2×n的一个长方形方格中，用一个1×2的骨牌铺满方格，输入n，输出铺放方案的总数。

解题思路：这是一道典型的动态规划问题。我们可以用f(n)表示铺满2×n方格的方案数。对于第一列，我们可以竖着放一块骨牌，这样就剩下2×(n-1)的方格需要铺满，方案数为f(n-1)；或者横着放两块骨牌，这样就剩下2×(n-2)的方格需要铺满，方案数为f(n-2)。因此，f(n)=f(n-1)+f(n-2)。

代码实现：

多米诺骨牌游戏，有N个骨牌，把它们摆在一条直线上，已知它们的位置和高度，骨牌可以向左右两边倒，若它可以碰到附近的骨牌（若它倒下去，只能达到附近骨牌位置时，不算能打倒，即：这里的骨牌是没有厚度的）问：任意推倒一块骨牌，最多能打倒多少张骨牌！用Java实现

以下是Java实现代码：

import java.util.Arrays;

public class DominoesGame {
    public static int knockDown(int[] positions, int[] heights, int index) {
        int n = positions.length;
        int[] left = new int[n]; // left[i]表示从位置i往左最多能打倒的骨牌数
        int[] right = new int[n]; // right[i]表示从位置i往右最多能打倒的骨牌数

        // 初始化
        Arrays.fill(left, 1);
        Arrays.fill(right, 1);

        // 计算left数组
        for (int i = index - 1; i >= 0; i--) {
            for (int j = i + 1; j <= index; j++) {
                if (positions[j] > positions[i]) {
                    int diff = heights[j] - heights[i];
                    if (diff <= 0 || diff > positions[j] - positions[i]) {
                        left[i] = Math.max(left[i], left[j] + 1);
                    }
                }
            }
        }

        // 计算right数组
        for (int i = index + 1; i < n; i++) {
            for (int j = i - 1; j >= index; j--) {
                if (positions[j] < positions[i]) {
                    int diff = heights[j] - heights[i];
                    if (diff <= 0 || diff > positions[i] - positions[j]) {
                        right[i] = Math.max(right[i], right[j] + 1);
                    }
                }
            }
        }

        // 计算结果
        int maxCount = 1;
        for (int i = 0; i < n; i++) {
            maxCount = Math.max(maxCount, left[i] + right[i] - 1);
        }
        return maxCount;
    }

    public static void main(String[] args) {
        int[] positions = {1, 3, 7, 8, 9};
        int[] heights = {1, 2, 6, 4, 3};
        int index = 2;
        int maxCount = knockDown(positions, heights, index);
        System.out.println("最多能打倒的骨牌数：" + maxCount); // 预期输出结果为4
    }
}

以上代码中，我们使用了动态规划的思想，分别计算了从每个位置往左和往右最多能打倒的骨牌数，然后取两者之和再减1即为任意推倒一块骨牌，最多能打倒的骨牌数。时间复杂度为O(n^2)，空间复杂度为O(n)。