1. 爬楼梯

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

解题思路：假设fn(n),表示爬山第n层的方法，那么爬山第n-1层就有fn(n-1)种方法,题中允许你走一次走一步或者两步，那么我们可以将最后一步固定，分为两种情况，最后一步是1和最后一步是2，当你最后走一个台阶时，走到n层的方法有fn(n-1)种，当你最后走两个台阶时，走到n层的方法有fn(n-1)，所以fn(n) = fn(n-1)+fn(n-2)，是否似曾相识---斐波那契数列。
参数解释在代码注释中

//remainStep代表剩余的阶梯数
//假设当前是第n层
//step1 登上第n-1层的方法数
//step2 登上第n-2层的方法数
int climb(int remainStep,int step1 = 1,int step2=1){
        //最后剩一个阶梯，那么登上第n层的方法数就是登上第n-1层的方法数；
        if( 1== remainStep)
              return step1;
        //假设当前层为第n层，登上第n+1层，那么
       //剩余的阶梯数就应该是remainStep-1
       //计算n+1层的方法就是就是fn(n)+fn(n-1)
       //fn(n ) = step1+step2;fn(n-1) = step1;
        return climb( remainStep-1, step1+step2,step1);
}
int climbStairs(int n) {
        return climb(n);
}

---

2. 买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

解题思路：依次遍历，记录已遍历过的子序列中最小的数min和最大的收益maxPrice，例如：
已知前n-1项中最大收益maxPrice，最小值min
当prices[n] -min > maxPrice时，则最大收益变大,maxPrice = prices[n] -min
当prices[n] < min时，前n项最小值变小，min = prices[n]

 int maxProfit(vector<int>& prices)
    {
      if(2 > prices.size())
          return 0;
      int min = prices[0];
      int maxPrice = 0;
      for(int i =1;i < prices.size();++i)
      {
          if( prices[i] > min)
              maxPrice = maxPrice > (prices[i] - min)? maxPrice:(prices[i]-min);
          else
              min = prices[i];

      }
      return maxPrice;
    }
};

---

3. 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

解题思路：顺序遍历，假设：
已知:
以prices[n-1]为最后元素的最大和是preMaxPrice
当前记录中存在最大的和时maxPrice
所求：以prices[n]为最后元素的最大和
因为前n-1个的最大和已知，我们只需要判断preMaxPrice+prices[n]与prices[n]的大小，如果prices[n]足够大，那么以prices[n]为结尾元素的最大和就是它自身，即序列是以n开始以n结束，赋值给preMaxPrice，此时的preMaxPrice就代表了以n为结尾的最大和。
我们之前已经保存了到目前位置出现最大和的最大值是maxPrice,所以我们需要将其与新出现的最大和比较大小，然后记录当前出现的最大值的最大和。

int maxSubArray(vector<int>& prices)
  {
      if( 0 >= prices.size())
          return 0;
      int maxPrice = prices[0];
      int preMaxPrice = prices[0] ;
      for(int i = 1;i < prices.size();++i)
      {
          preMaxPrice = max(preMaxPrice+prices[i],prices[i]);

          maxPrice = max(maxPrice,preMaxPrice);
      }
      return maxPrice;
  }

---

4. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

• 示例
  输入: [2,7,9,3,1]
  输出: 12
  解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
  偷窃到的最高金额 = 2 + 9 + 1 = 12 。

解题思路：此题的核心思想就是当前这家是否有打结的必要。
已知：
1.打劫第n-2家时的总金额是pre2
2.打劫到第n-1家时的总金额是pre1
求：是否打劫第n家？
进入到第n家时，如果打劫第n家，那么总金额是 pre2+nums[n]
如果只是看看，不打劫，那么总金额是pre1。
所以是否打劫第n家，就要看pre1和pre2+nums[n]谁更大，谁就是搜索到第n家时，盗贼兜里钱的总和。由于数组都是正整数所以pre1,pre2一定是不变或者递增，然后为n+1家计算pre1和pre2，继续遍历直到结束，那么pre1就是n家时所窃取的财富，pre2就是n-1 家所窃取的财富，返回二者之间的最大值即可。

int rob(vector<int>& nums) {
        if(0 >= nums.size())
            return 0;
        if(1== nums.size())
            return nums[0];
        int pre2 = 0;
        int pre1 = nums[0];
        for(int i = 1;i< nums.size();++i)
        {
            int temp = pre2+nums[i];
            pre2 = pre1;
            pre1 = max(pre1,temp);
        }
        return max(pre2,pre1);
    }