LeetCode热题100——动态规划

1. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

// 题解：每次都有两种选择，1或者2
int climbStairs(int n) {
	if (n <= 0) return 0;
	vector<int> dp(n+1, 0);
	dp[0] = 1;
	dp[1] = 1;
	for (int i = 2; i <= n; ++i) {
		dp[i] = dp[i-1] + dp[i-2];
	}
	return dp[n];
}

2. 杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。

// 题解：从第三层开始，累计和
vector<vector<int>> generate(int numRows) {
	vector<vector<int>> result(numRows);
	for (int i = 0; i < numRows; ++i) {
		result[i].resize(i+1);
		reult[i][0] = result[i][i] = 1;
		for (int j = 1; j < i; ++j) {
			result[i][j] = result[i-1][j] + result[i-1][j-1];
		}
	}
	return result;
}

3. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

// 题解：和上次结果比较，取最大值
int rob(vector<int>& nums) {
	int length = nums.size();
	if (length == 0) return 0;
	
	vector<int> dp(length+1, 0);
	dp[1] = nums[0];
	for (int i = 2; i <= length; ++i) {
		dp[i] = max(dp[i-1], dp[i-2] + nums[i-1]);
	}
	return dp[length];
}