[TOC]
## 统计方案
### 题目描述
在一无限大的二维平面中，我们做如下假设： 1、每次只能移动一格； 2、不能向后走（假设你的目的地是“向上”，那么你可以向左走，可以向右走，也可以向上走，但是不可以向下走）； 3、走过的格子立即塌陷无法再走第二次。 求走n步不同的方案数（2种走法只要有一步不一样，即被认为是不同的方案）。
* * * * *
### 输入
首先给出一个正整数C，表示有C组测试数据。 接下来的C行，每行包含一个整数n（n<=20），表示要走n步。
* * * * *
### 输出
请编程出走n步的不同方案总数； 每组的输出占一行
* * * * *
### 代码实现
```
#include<iostream>
using namespace std;
int move(int n){
if(n == 1){
return 3;
}else if(n == 2){
return 7;
}else{
return 2*move(n-1) + move(n-2);
}
}
int main(){
int n,cur;
cin >> n;
for(int i = 0; i < n; i ++){
cin >> cur;
cout << move(cur) << endl;
}
}
```
### 分析
区间调度是贪心算法的一种典型例题，对于区间调度，普遍的解法是将结构体或数组按照结束时间排序，我们的策略是优先选取结束时间早的时间，这样可以尽可能选择多的事件。
* * * * *
核心代码如下
```
int pos = 0;
int cnt = 0;
for(int i = 0; i < n; i ++){
if( pos <= nodes[i].start ){
cnt += 1;
pos = nodes[i].end;
}
}
```
用pos来存储结束时间，cnt用来表示可以参加多少件事件，如果当前结束时间小于或者等于下一个事件的开始时间，我们就将cnt加一
