855学习记录算法刷题$Day$-$4$——炎泽汐$de$ Blog

零钱兑换

---

     完全背包问题；

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;
        for(int i = 1; i <= amount; i++){
            for(int j = 0; j < n; j++){
                if(coins[j] <= i){
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] <= amount ? dp[amount] : -1;
    }
};

打家劫舍 3

---

      树上 DP，DFS，偷为 a 不偷为 b，注意父节点不偷子节点偷不偷均可，父节点偷子节点只能不偷；

class Solution {
public:
    struct dpnode{
        int a, b;
        dpnode(int x, int y) : a(x), b(y) {}
    };

    dpnode dfs(TreeNode* root){
        if(!root){
            return dpnode(0, 0);
        }
        dpnode ans = dpnode(0, 0);
        dpnode t1 = dfs(root -> left);
        dpnode t2 = dfs(root -> right);
        ans.a = t1.b + t2.b + root -> val;
        ans.b = max(t1.a, t1.b) + max(t2.a, t2.b);
        return ans;
    }
    int rob(TreeNode* root) {
        dpnode ans = dfs(root);
        return max(ans.a, ans.b);
    }
};

分割等和子集

---

     背包问题

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int amount = 0, n = nums.size(), maxn = 0;
        for(int i = 0; i < n; i++){
            amount += nums[i];
            maxn = max(maxn, nums[i]);
        }
        if(amount & 1 || maxn * 2 > amount){
            return false;
        }else{
            amount = amount >> 1;
            vector<int> dp(amount + 1, 0);
            dp[0] = true;
            for(int i = 0; i < n; i++){
                int num = nums[i];
                for(int j = amount; j >= num; j--){
                    dp[j] |= dp[j - num];
                }
            }
            return dp[amount];
        }
    }
};

目标和

---

      笨方法 DP；

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int amount = 0, n = nums.size();
        for(int i = 0; i < n; i++){
            amount += nums[i];
        }

        if(amount < abs(target)){
            return 0;
        }

        int dp[n][amount + 1];
        memset(dp, 0, sizeof(dp));

        if(nums[0] == 0){
            dp[0][nums[0]] = 2;
        }else{
            dp[0][nums[0]] = 1;
        }
        for(int i = 1; i < n; i++){
            for(int j = 0; j <= amount; j++){
                if(nums[i] == 0){
                    dp[i][j] = dp[i - 1][j] * 2;
                }else{
                    if(j >= nums[i]){
                        dp[i][j] += dp[i - 1][j - nums[i]];
                    }else{
                        dp[i][j] += dp[i - 1][abs(j - nums[i])];
                    }
                    if(j + nums[i] <= amount){
                        dp[i][j] += dp[i - 1][j + nums[i]];
                    }
                }
            }
        }

        return dp[n - 1][abs(target)];
    }
};

      优化分两个集合一个是正组成的，一个是负组成的，所以正之和应为(sum + target)/2；

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int amount = 0, n = nums.size();
        for(int i = 0; i < n; i++){
            amount += nums[i];
        }

        if(amount < abs(target) || (amount + target) & 1 == 1){
            return 0;
        }

        amount = (target + amount) >> 1;

        int dp[amount + 1];
        memset(dp, 0, sizeof(dp));

        dp[0] = 1;
        for(int num : nums){
            for(int j = amount; j >= num; j--){
                dp[j] += dp[j - num];
            }
        }

        return dp[amount];
    }
};

回文子串

---

     逻辑和最长回文子串一样，中心扩散；

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size(),ans = 0;
        int dp[n][n];
        memset(dp,0,sizeof(dp));

        for(int i = 0;i < n;i++){
            dp[i][i] = 1;
            ans++;
        }

        for(int i = n - 1;i >= 0;i--){
            for(int j = i + 1;j < n;j++){
                if(s[i] == s[j] && (j - i == 1 || dp[i + 1][j - 1] == 1)){
                    dp[i][j] = 1;
                    dp[j][i] = 1;
                    ans++ ;
                }
            }
        }
        return ans;
    }
};