爬楼梯

你正在爬楼梯。需要 n 步你才能到达顶部。每次你可以爬 1 或 2 个台阶。你有多少种不同的方式可以爬到楼顶呢？给定 n 将是一个正整数。

示例 1：输入： 2
输出： 2
说明： 有两种方法可以爬到顶端。1.  1 步 + 1 步
2.  2 步示例 2：输入： 3
输出： 3
说明： 有三种方法可以爬到顶端。1.  1 步 + 1 步 + 1 步
2.  1 步 + 2 步
3.  2 步 + 1 步

分析:
n=1时;步数step=1
n=2时;步数step=2
n=3时;步数step=3
n=4时;步数step=5
...
f(n)=f(n-1)+f(n-2)

vector<int> save;
int climbStairs(int n) {if(n==1)return 1;if(n==2)return 2;if(save.size()>(n-2))return save[n-3];save.push_back(climbStairs(n-1)+climbStairs(n-2));return save.back();
}

最大子序和

给定一个序列（至少含有 1 个数），从该序列中寻找一个连续的子序列，使得子序列的和最大。

例如，给定序列 [-2,1,-3,4,-1,2,1,-5,4]，
连续子序列 [4,-1,2,1] 的和最大，为 6。

分析:
nums:[-2,1,-3,4,-1,2,1,-5,4]
tmp:[-2,1,-2,4,3,5,6,1,5]tmp[0]=nums[0]
tmp[1]=max(nums[1],tmp[0]+nums[1])
tmp[2]=max(nums[2],tmp[1]+nums[2])
...
tmp[n]=max(nums[n],tmp[n-1]+nums[n])

int maxSubArray(vector<int>& nums) {vector<int> tmp;tmp.push_back(nums[0]);for(int i=1;i<nums.size();i++)tmp.push_back(max(nums[i],tmp[i-1]+nums[i]));sort(tmp.begin(),tmp.end());return tmp.back();
}

打家劫舍

你是一个专业的强盗，计划抢劫沿街的房屋。每间房都藏有一定的现金，阻止你抢劫他们的唯一的制约因素就是相邻的房屋有保安系统连接，如果两间相邻的房屋在同一晚上被闯入，它会自动联系警方。给定一个代表每个房屋的金额的非负整数列表，确定你可以在没有提醒警方的情况下抢劫的最高金额。

分析:
nums:[2,1,2,4,3]
tmp:[2,2,4,6,7]tmp[0]=nums[0];
tmp[1]=max(nums[0],nums[1])
tmp[2]=max(nums[2]+tmp[0],tmp[1])
...
tmp[n]=max(nums[n]+tmp[n-2],tmp[n-1])

int rob(vector<int>& nums) {if(!nums.size())return 0;if(nums.size()==1)return nums[0];vector<int> tmp;tmp.push_back(nums[0]);tmp.push_back(max(nums[0],nums[1]));for(int i=2;i<nums.size();i++)tmp.push_back(max(nums[i]+tmp[i-2],tmp[i-1]));return tmp.back();
}