每日两题 / 198. 打家劫舍 && 74. 搜索二维矩阵（LeetCode热题100）

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

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

class Solution {
public:
#define N 110
    int 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);
    }
};