买卖股票的最佳时机

  1. 输入: [7,1,5,3,6,4]
  2. 输出: 5
  3. 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
  4.      注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

一次解决股票买卖问题：
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/yi-ge-fang-fa-tuan-mie-6-dao-gu-piao-wen-ti-by-l-3/

  1. class Solution {
  2. public:
  3.     int maxProfit(vector<int>& prices) {
  4.         const int n = prices.size();
  5.         if(n == 0) return 0;
  6.         int dp[n][2];
  7.         for(int i = 0; i < n; i++){
  8.             if(i - 1 == -1){
  9.                 dp[i][0] = 0;
  10.                 dp[i][1] = -prices[i];
  11.                 continue;
  12.             }
  13.             dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
  14.             dp[i][1] = max(dp[i - 1][1], -prices[i]);
  15.         }
  16.         return dp[n - 1][0];
  17.     }
  18. };
  20. dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
  21.               max(   选择 rest  ,           选择 sell      )
  23. 解释：今天我没有持有股票，有两种可能：
  24. 要么是我昨天就没有持有，然后今天选择 rest，所以我今天还是没有持有；
  25. 要么是我昨天持有股票，但是今天我 sell 了，所以我今天没有持有股票了。
  27. dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
  28.               max(   选择 rest  ,           选择 buy         )
  30. 解释：今天我持有着股票，有两种可能：
  31. 要么我昨天就持有着股票，然后今天选择 rest，所以我今天还持有着股票；
  32. 要么我昨天本没有持有，但今天我选择 buy，所以今天我就持有股票了。

打家劫舍

  1. 输入: [1,2,3,1]
  2. 输出: 4
  3. 解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
  4.      偷窃到的最高金额 = 1 + 3 = 4 。

简洁写法

  1. class Solution {
  2. public:
  3.     int rob(vector<int>& nums) {
  4.         const int n = nums.size();
  5.         if(n == 0) return 0;
  6.         int dp[n + 1];
  7.         dp[0] = 0;
  8.         dp[1] = nums[0];
  9.         for(int i = 2; i <= n; i++){
  10.             dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]);
  11.         }
  12.         return dp[n];
  13.     }
  14. };

我自己写的

  1. class Solution {
  2. public:
  3.     int rob(vector<int>& nums) {
  4.         const int n = nums.size();
  5.         if(n == 0) return 0;
  6.         int dp[n][2];
  7.         //0代表没偷，1代表偷了
  8.         dp[0][0] = 0;
  9.         dp[0][1] = nums[0];
  10.         int ans = nums[0];
  11.         for(int i = 1; i < n; i++){
  12.             dp[i][1] = dp[i - 1][0] + nums[i];
  13.             dp[i][0] = max(dp[i - 1][1], dp[i - 1][0]);
  14.             ans = max(ans, max(dp[i][1], dp[i][0]));
  15.         }
  16.         return ans;
  17.     }
  18. };

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

  1. class Solution {
  2. public:
  3.     bool isSubsequence(string s, string t) {
  4.         int flag = 0;
  5.         if(s.size() == 0) return true;
  6.         for(int i = 0;i < t.size(); i++){
  7.             if(t[i] == s[flag]) {
  8.                 flag++;
  9.                 if(flag == s.size())return true;
  10.             }
  11.         }
  12.         return false;
  13.     }
  14. };

花费最少代价爬楼梯

  1. 数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i](索引从0开始)。
  2. 每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。
  3. 您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。
  5. 示例 1:
  6. 输入: cost = [10, 15, 20]
  7. 输出: 15
  8. 解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。
  1. class Solution {
  2. public:
  3.     int minCostClimbingStairs(vector<int>& cost) {
  4.         const int n = cost.size();
  5.         vector<int> dp(n + 1);
  6.         //dp[i]的含义是到达i层之前所花费的代价
  7.         dp[0] = 0;
  8.         dp[1] = 0;
  9.         for(int i = 2; i <= n; i++){
  10.             dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
  11.         }
  12.         return dp[n];
  13.     }
  14. };

三步问题

  1. 三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。
  1. class Solution {
  2. public:
  3.     int waysToStep(int n) {
  4.         vector<long long> dp(n + 1);
  5.         if(n <= 2) return n;
  6.         if(n == 3) return 4;
  7.         dp[1] = 1, dp[2] = 2, dp[3] = 4;
  8.         for(int i = 4; i <= n; i++){
  9.             dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % (1000000007);
  10.         }
  11.         return dp[n];
  12.     }
  13. };

最大连续子列和

  1. 输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
  2. 要求时间复杂度为O(n)。
  3. 示例1:
  5. 输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
  6. 输出: 6
  7. 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
  1. class Solution {
  2. public:
  3.     int maxSubArray(vector<int>& nums) {
  4.         int len = nums.size();
  5.         vector<int> dp(len);
  6.         dp[0] = nums[0];
  7.         int maxnum = dp[0];
  8.         for(int i = 1; i < len; i++){
  9.             dp[i] = max(nums[i], dp[i - 1] + nums[i]);
  10.             if(dp[i] > maxnum) maxnum = dp[i];
  11.         }
  12.         return maxnum;
  13.     }
  14. };

按摩师

  1. 一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
  2. 输入： [2,7,9,3,1]
  3. 输出： 12
  4. 解释： 选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。
  1. class Solution {
  2. public:
  3.     int massage(vector<int>& nums) {
  4.         int len = nums.size();
  5.         if(len == 0) return 0;
  6.         if(len == 1) return nums[0];
  7.         vector<int>dp(len);
  8.         dp[0] = nums[0];
  9.         dp[1] = max(nums[0], nums[1]); 
  10.         for(int i = 2; i < len; i++){
  11.             dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
  12.         }
  13.         return dp[len - 1];
  14.     }
  15. };