目录

• 题目描述
• 示例
• 输入
• 输出
• 说明
• 分析
• 代码
• 动规
• 贪心

题目描述

在一条直的马路上，有n棵树，每棵树有一个坐标，代表它们距离马路起点的距离。 如果每相邻的两棵树之间的间隔不小于d，那么我们认为这些树是美观的。 请计算出最少移除多少棵树，可以让这些树变得美观。
树木的棵树为n，1<=n<=1e5。 树木的坐标用trees[]表示，0<=trees[i]<=1e9。最小美观间隔为d，1<=d<=1e9。保证输入的坐标是排好序的，且两两不相同。

示例

输入

[1,2,3,5,6]
2

输出

2

说明

样例中，将位置2与6的树木移走，剩下[1,3,5]，它们是美观的。

分析

我在一开始把这道题目当作了比较简单的动规。保证相邻两颗树的距离不小于d，这是个很明显的最优子问题结构。
设dp[i]为保留树木i作为最后一棵树木时留下树木的最大数量。遍历所有的j<i，当tree i与tree j的距离不低于d时，更新dp。状态转移方程为：

dp[i]=max(dp[i],dp[j]+1)

后面想到可以用贪心去解决。可以证明：最后一棵树一定可以保留，向前依次取距离满足条件的所有树即可。或是保留第一棵树，之后向后遍历，如果当前的树与上一棵选中的树之间的距离大于等于d，那么就保留这棵树，否则移除。

证明过程为：假设最终的最优解不可以包括最后一棵树，那么假设最优解中最后一棵树为I(n)，倒数第二棵树为I(n-1)。则有trees[I(n)]-trees[I(n-1)]>=d。由于最后一棵树j一定满足trees[j]>trees[I(n)]，因此一定有trees[j]-trees[I(n-1)]>d。所以不选择树I(n)，而是选择j是完全可以的，因此保留最后一棵树一定可以得到最优解。以此类推，每次选择当前满足条件的最后面一棵树，问题解决。

显然动规算法的时间复杂度为O(N^2)，贪心算法的时间复杂度为O(N)。

代码

动规

#include <vector>
#include <iostream>
using namespace std;
class Solution {
	public:
		int treePlanning(vector<int> &trees, int d) {
			// write your code here.
			int dp[trees.size()];
			for(int i=0; i<trees.size(); i++)
				dp[i]=1;
			for(int i=1; i<trees.size(); i++) {
				for(int j=0; j<i&&trees[i]-trees[j]>=d; j++) {
					dp[i]=max(dp[i],dp[j]+1);
				}
			}
			int max=0;
			for(int i=0; i<trees.size(); i++){
				cout<<dp[i]<<" ";
				if(dp[i]>max)
					max=dp[i];
			}
			return trees.size()-max;
		}
};
int main() {
	vector<int> v;
	v.push_back(0);
	v.push_back(2);
	v.push_back(3);
	v.push_back(5);
	v.push_back(6);
	v.push_back(9);
	v.push_back(10);
	v.push_back(13);
	v.push_back(14);
	v.push_back(15);
	Solution s;
	cout<<endl<<s.treePlanning(v,2);
	return 0;
}

贪心

class Solution {
	public:
		int treePlanning(vector<int> &trees, int d) {
			// write your code here.
			int count=1;
			int curr=trees.size()-1;
			while(1) {
				int j=curr-1;
				while(j>=0&&trees[curr]-trees[j]<d) {
					j--;
				}
				if(j<0)
					break;
				if(trees[curr]-trees[j]>=d)
					curr=j;
				count++;
			}
			return trees.size()-count;
		}
};