首页 computer-science algorithm leetCode

1679113530800

# 算法解释

1679113639440

# 基本动态规划：一维

# 70. Climbing Stairs (Easy)

https://leetcode.com/problems/climbing-stairs/

1679116338307

1679116353109

# 198. House Robber (Easy)

https://leetcode.com/problems/house-robber/

1679116608551

1679116621374

class Solution {
public:
    int rob(vector<int> &nums) {
        vector<int> dp(nums.size(), 0);
        dp[0] = nums[0];
        if (nums.size() >= 2) {
            dp[1] = max(nums[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];
    }
};
# 413. Arithmetic Slices (Medium)
https://leetcode.com/problems/arithmetic-slices/
1679117053893
1679117248415
注意：子数组的元素个数至少是 3 个。
class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        vector<int> dp(nums.size(), 0);
        for(int i = 2; i < nums.size(); i++) {
            if(nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) {
                dp[i] = dp[i-1] + 1;
                //dp [i-1] 表示在以 num [i-1] 后接上一个 num [i]，维持 dp [i-1] 的数量
                // + 1 表示 nums [i-2]、nums [i-1]、nums [i]
            }
        }
        return accumulate(dp.begin(), dp.end(), 0);
    }
};
# 416. Partition Equal Subset Sum (Medium)
https://leetcode.cn/problems/partition-equal-subset-sum/
1679291499116
# 1143. Longest Commom Subsequence (Medium)
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.length(), n = text2.length();
        vector<vector<int> > dp(m+1, vector<int>(n+1, 0));
        
        for(int i = 1; i <=m; i++) {
            for(int j = 1; j <= n; j++) {
                if(text1[i-1] == text2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] +1;
                }else{
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        
        return dp[m][n];
    }
};
# 背包问题
# 322. Coin Change (Medium)
注意：初始化为 amount + 1 即可，全用 1 元硬币时的数量最多，为 amount 个。
dp 数组的下标表示容量
class Solution {
public:
    int coinChange(vector<int> &coins, int amount) {
        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (const int &coin: coins) {
                if (i >= coin) {
                    dp[i] = min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }
};
# 474. Ones and Zeroes (Medium)
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        //m 个 0，n 个 1
        vector< vector<int> > dp(m+1, vector<int>(n+1, 0));
        // 初始化
        // 循环
        for(const string str: strs) {
            auto [count0, count1] = count(str);
            for(int i = m; i >= count0; i--) {
                for(int j = n; j >= count1; j--) {
                    dp[i][j] = max(dp[i][j], dp[i-count0][j-count1] + 1);
                }
            }
        }
        return dp[m][n];
    }
    pair<int, int> count(string str) {
        int count0 = str.length(), count1 = 0;
        for(int i = 0; i < str.length(); i++) {
            if(str[i] == '1') {
                count1++;
                count0--;
            }
        }
        return pair<int, int>(count0, count1);
    }
};
# 416. Partition Equal Subset Sum (Medium)
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if(sum % 2) {
            return false;
        }
        sum = sum / 2;
        vector<bool> dp(sum+1, false);
        dp[0] = true;
        for(const int num: nums) {
            for(int i = sum; i >= num; i--) {
                dp[i] = dp[i] || dp[i - num];
            }
        }
        return dp[sum];
    }
};