2024-10-05

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

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        // 0. Move index to 1-based
        nums.insert(nums.begin(), 0);
        // 1. Define f, initialize -oo
        vector<vector<int>> f(n + 1, vector<int>(2, -1e9));
        f[0][0] = 0;
        // 2. Loop over all states
        for (int i = 1; i <= n; i++) {
            // 3. Copy decision funcs
            f[i][0] = max(f[i - 1][0], f[i - 1][1]);
            f[i][1] = f[i - 1][0] + nums[i];
        }
        // 4. Return target
        return max(f[n][0], f[n][1]);
    }
};

2. 213. 打家劫舍 II - 力扣（LeetCode）

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];
        nums.insert(nums.begin(), 0);
        vector<vector<int>> f(n + 1, vector<int>(2, -1e9));
        // 将环强行断开
        // 情况1：偷1号，n号不偷
        f[1][0] = 0; // !!!偷1号时，也要初始化f[1][0]
        f[1][1] = nums[1];
        for (int i = 2; i <= n; i++) {
            f[i][1] = f[i - 1][0] + nums[i];
            f[i][0] = max(f[i - 1][0], f[i - 1][1]);
        }
        int ans = f[n][0];
        // 情况2：不偷1号，n号随意
        f[1][0] = 0;
        f[1][1] = -1e9; // !!!需要再重新赋初值
        for (int i = 2; i <= n; i++) {
            f[i][1] = f[i - 1][0] + nums[i];
            f[i][0] = max(f[i - 1][0], f[i - 1][1]);
        }
        return max(ans, max(f[n][0], f[n][1]));
    }
};

3. 72. 编辑距离 - 力扣（LeetCode）

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.length(), n = word2.length();
        // 0. Move index to 1-based
        word1 = " " + word1, word2 = " " + word2;
        // 1. Define f, initialize -oo
        vector<vector<int>> f(m + 1, vector<int>(n + 1, 1e9));
        for (int i = 0; i <= m; i++) f[i][0] = i;
        for (int j = 0; j <= n; j++) f[0][j] = j;
        // 2. Loop over all states
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++) 
                // 3. Copy decision funcs
                f[i][j] = min(min(f[i - 1][j] + 1, f[i][j - 1] + 1),
                        f[i - 1][j - 1] + (word1[i] != word2[j]));
        // 4. Return target
        return f[m][n];
    }
};

4. 416. 分割等和子集 - 力扣（LeetCode）

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        for (int i = 0; i < n; i++) sum += nums[i];
        if (sum % 2 == 1) return false;
        // 0. Move index to 1-based
        nums.insert(nums.begin(), 0);
        // 1. Define f, initialize -oo
        vector<int> f(sum / 2 + 1, false);
        f[0] = true;
        // 2. Loop over all states
        for (int i = 1; i <= n; i++)
            for (int j = sum / 2; j >= nums[i]; j--)
                // 3. Copy decision funcs
                f[j] |= f[j - nums[i]];
        // 4. Return target
        return f[sum / 2];
        /*
        // 1. Define f, initialize -oo
        vector<vector<int>> f(n + 1, vector<int>(sum + 1, false));
        f[0][0] = true;
        // 2. Loop over all states
        for (int i = 1; i <= n; i++)
            for (int j = 0; j <= sum; j++) {
                // 3. Copy decision funcs
                // 此处相当于直接拷贝，所以优化思路：直接原地拷贝
                f[i][j] = f[i - 1][j];
                if (j >= nums[i])
                    f[i][j] = f[i - 1][j - nums[i]] || f[i - 1][j];
            }
        return f[n][sum / 2];
        */
    }
};

5. 518. 零钱兑换 II - 力扣（LeetCode）
   力扣第29测试过不去

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        coins.insert(coins.begin(), 0);
        vector<int> f(amount + 1, 0);
        f[0] = 1;
        for (int i = 1; i <= n; i++)
            for (int j = coins[i]; j <= amount; j++)
                f[j] += f[j - coins[i]];
        return f[amount];
    }
};