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

思路：
设跳上 n 级台阶有 f(n) 种跳法。在所有跳法中，青蛙的最后一步只有两种情况： 跳上 1 级或 2 级台阶。

当为 1 级台阶： 剩 n−1 个台阶，此情况共有 f(n−1) 种跳法。
当为 2 级台阶： 剩 n−2 个台阶，此情况共有 f(n−2) 种跳法。
即 f(n)为以上两种情况之和，即 f(n)=f(n−1)+f(n−2)，以上递推性质为斐波那契数列。

动态规划解析：
状态定义： 设 dp 为一维数组，其中 dp[i] 的值代表斐波那契数列的第 i 个数字。
转移方程： dp[i+1]=dp[i]+dp[i−1]，即对应数列定义 f(n+1)=f(n)+f(n−1)。
初始状态： dp[0]=1, dp[1]=1，即初始化前两个数字。
返回值： dp[n]，即斐波那契数列的第 n 个数字。

状态压缩：
若新建长度为 n 的 dp 列表，则空间复杂度为 O(N) 。

由于 dp 列表第 i 项只与第 i−1 和第 i−2 项有关，因此只需要初始化三个整形变量 sum, a, b ，利用辅助变量 sum 使 a,b 两数字交替前进即可 （具体实现见代码） 。由于省去了 dp 列表空间，因此空间复杂度降至 O(1)。

class Solution
{
public:
	int climbStairs(int n)
	{
		int a = 1, b = 1, sum;
		for(int i = 0; i<n-1; i++)
		{
			sum = a + b;
			a = b;
			b = sum;
		}
		return b;
	}
};

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


思路：
把杨辉三角的每一排左对齐：

设要计算的二维数组是 c，计算方法如下：
每一排的第一个数和最后一个数都是 111，即 c[i][0]=c[i][i]=1。
其余数字，等于左上方的数，加上正上方的数，即 c[i][j]=c[i−1][j−1]+c[i−1][j]。例如 4=1+3, 6=3+3等。

class Solution
{
public:
	vector<vector<int>> generate(int numRows)
	{
		vector<vector<int>> c(numRows);
		for(int i = 0; i<numRows; i++)
		{
			// 左对齐
			c[i].resize(i+1,1);
			for(int j = 1; j<i; j++)
			{
				// 左上方 + 正上方
				c[i][j] = c[i-1][j] + c[i-1][j-1];
			}
		}
		return c;
	}
};