面试题 17.16. 按摩师

image.png

  1. class Solution {
  2. public:
  3.     int massage(vector<int>& nums) {
  4.         int size = nums.size();
  5.         if(size == 0) return 0; 
  6.         if(size == 1) return nums[0];
  8.         vector<int> dp(size, 0);
  9.         dp[0] = nums[0]; //dp[i] 表示nums[0...i] 能得到的最长时间
  10.         dp[1] = max(nums[0],nums[1]);
  12.         for(int i = 2; i < size; i++)
  13.         {
  14.             //遍历迄今为止的最大值，两种情况取较大：
  15.             //1：预约本次，则上一次不预约（dp[i-2] + nums[i]）
  16.             //2：本次不预约，则值为预约到上一次的最大值
  17.             dp[i] = max(dp[i-2] + nums[i], dp[i-1]);
  18.         }
  19.         return dp[size -1];
  20.     }
  21. };

198. 打家劫舍

image.png

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

213. 打家劫舍 II

image.png

  1. class Solution {
  2. public:
  3.     int rob(vector<int>& nums) {
  4.         if(nums.size()==0) return 0;
  5.         if(nums.size()==1) return nums[0];
  6.         if(nums.size()==2) return max(nums[0],nums[1]);
  7.         if(nums.size()==3) return max(max(nums[0],nums[1]),nums[2]);
  8.         int n = nums.size();
  10.         //0——n-1
  11.         vector<int> dp(n-1,0);
  12.         dp[0]=nums[0];
  13.         dp[1]=max(nums[0],nums[1]);
  14.         for(int i=2;i<dp.size();i++)
  15.         {
  16.             dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
  17.         }
  19.         //1-n
  20.         vector<int> dpp(n,0);
  21.         dpp[1]=nums[1];
  22.         dpp[2]=max(nums[2],nums[1]);
  23.         for(int i=3;i<dpp.size();i++)
  24.         {
  25.             dpp[i]=max(dpp[i-1],dpp[i-2]+nums[i]);
  26.         }
  27.         return max(dp.back(),dpp.back());
  28.     }
  29. };

1. 盛最多水的容器

image.png

class Solution {
public:
int maxArea(vector<int>& height) {
    int res = 0;
    int i = 0;
    int j = height.size() - 1;
    while (i < j) {
        int area = (j - i) * min(height[i], height[j]);
        res = max(res, area);
        if (height[i] < height[j]) {
            i++;
        } else {
            j--;
        }
    }
    return res;
}
};