[算法设计]斐波拉契优化与区间不相交问题

斐波拉契数,最基本的定义用递归,现利用”自底向上”的思路求解:

#include <cstdio>
#include <ctime>

int BaseFib(int n) {//暴力递归斐波拉契数列
	if (n == 1 || n == 2) return 1; //递归出口
	return BaseFib(n - 1) + BaseFib(n - 2);
}

int DpTableFib(int n) {//dpTable,自底向上
	int dp[1000] = {0}; //初始化为0
	dp[1] = 1;
	dp[2] = 1;
	for (int i = 3; i <= n; ++i) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	return dp[n];
}


int main() {
	int n = 20;
	int m = n;
	printf("%d", BaseFib(n));
	printf("%d", DpTableFib(m));
	return 0;
}

不相交子区间问题

/*
区间不相交问题
*/
#include <algorithm>
using namespace std;

const int MaxN = 10;
struct interval
{
	int x, y; //开区间左右端点
} I[MaxN];

bool cmp(interval a, interval b) {
	if (a.x != b.x) return a.x > b.x; //先按照左端点从大到小的顺序排序
	return a.y < b.y; // 如果左端点相同, 则按照右端点从小到大的顺序排序
}


int main() {
	int n;
	while (scanf_s("%d", &n), n!=0){
		for (int i = 0; i < n; ++i) {
			scanf_s("%d%d", &I[i].x, &I[i].y);
		}
		sort(I, I + n, cmp);
		int ans = 1, lastX = I[0].x;
		for (int i = 1; i < n; ++i) {
			if (I[i].y <= lastX) {
				lastX = I[i].x;
				ans++;
			}
		}
		printf("%d",ans);
	}
	return 0;
}