198. 打家劫舍 - 力扣（LeetCode）

dp[i]表示考虑前i + 1号房屋，能获取的最大金额。对于没一间房屋都有偷与不偷两种选择
如果偷，需要从dp[i - 2]转移，因为不能偷窃相邻房屋，dp[i] = dp[i - 2] + nums[i]
如果不偷，则从dp[i - 1]转移，此时可以偷窃相邻房屋
我们需要从两种选择中，取最大值

class Solution {
public:
#define N 110int dp[N];int rob(vector<int>& nums) {dp[0] = nums[0];if (nums.size() > 1) dp[1] = max(dp[0], nums[1]);for (int i = 2; i < nums.size(); ++ i) {dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);}return dp[nums.size() - 1];}
};

---

74. 搜索二维矩阵 - 力扣（LeetCode）

如果当前行的第一个元素小于等于target并且下一行的第一个元素大于target，那么target只可能存在与当前行

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int l = 0;int n = matrix.size(), m = matrix[0].size();while (l < n && matrix[l][0] <= target) l ++ ;if (l) l -- ;return binary_search(matrix[l].begin(), matrix[l].end(), target);}
};