ch10-of-programmercarl-2

C++ C 代码随想录 背包问题 动态规划
刷题
发布日期:   2022-04-19

1 一和零

1.1 题目描述

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例1:

输入: strs = [“10”, “0001”, “111001”, “1”, “0”], m = 5, n = 3
输出: 4
解释: 最多有 5 个 0 和 3 个 1 的最大子集是 {“10”,”0001”,”1”,”0”} ，因此答案是 4 。
其他满足题意但较小的子集包括 {“0001”,”1”} 和 {“10”,”1”,”0”} 。{“111001”} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例2:

输入: strs = [“10”, “0”, “1”], m = 1, n = 1
输出: 2
解释: 最大的子集是 {“0”, “1”} ，所以答案是 2 。

1.2 思路

  其实就是两重01背包，看作有两个背包，一个装0一个装1, 其容量分别为m和n，某个物品放入背包的条件是同时可以被放入0背包和1背包中。

完整代码如下：

  • Cpp 实现
class Solution {
public:
    int countOnes(string strs){
        int ones = 0;
        for(char ch: strs){
            if(ch == '0'){
                continue;
            }
            ++ones;
        }
        return ones;
    }

    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<pair<int, int>> weight;
        for(string str: strs){
            int ones = countOnes(str);
            weight.emplace_back(make_pair(str.length()-ones, ones));
        }
        int dp[m+1][n+1];
        memset(dp, 0, sizeof(dp));
        for(int i = 0; i < strs.size(); ++i){
            for(int j = m; j >= weight[i].first; --j){
                for(int k = n; k >= weight[i].second; --k){
                    dp[j][k] = max(dp[j][k], dp[j-weight[i].first][k-weight[i].second]+1);
                }
            }
        }
        return dp[m][n];
    }
};
  • C 实现
int findMaxForm(char ** strs, int strsSize, int m, int n){
    //遍历字符串数组，统计每个字符串的0和1的个数
    int cost[strsSize][2];     //0,1两种cost
    for(int i = 0; i < strsSize; i++){      //将每个字符串的0和1提取出来
        cost[i][0] = cost[i][1] = 0;
        for(int j = 0; j < strlen(strs[i]); j++){
            if(strs[i][j] == '0'){          //cost[.][0]存放0的个数
                cost[i][0]++;
            }else{                          //cost[.][1]存放1的个数
                cost[i][1]++;
            }
        }
    }
    //dp数组初始化
    /*int dp[m+1][n+1][strsSize];             //row为0的容量, col为1的容量
    for(int row = 0; row <= m; row++){
        for(int col = 0; col <= n; col++){
            if(row >= cost[0][0] && col >= cost[0][1]){ //当背包两种容量都超过当前的物品的体积时才能放入
                dp[row][col][0] = 1;        
            }else{          
                dp[row][col][0] = 0;
            }
        }
    }
    //求解背包问题
    for(int layer = 1; layer < strsSize; layer++){  //layer即01背包中的物品
        for(int row = 0; row <= m; row++){    
            for(int col = 0; col <= n; col++){
                if(row>=cost[layer][0]&&col >= cost[layer][1]){ //防止索引出现负数报错
                    dp[row][col][layer] = fmax(dp[row][col][layer-1],dp[row-cost[layer][0]][col-cost[layer][1]][layer-1]+1);
                }else{
                    dp[row][col][layer] = dp[row][col][layer-1];
                }
            }
        }
    }*/
    //求解过程降维
    //dp数组初始化
    int dp[m+1][n+1];             //row为0的容量, col为1的容量
    for(int row = 0; row <= m; row++){
        for(int col = 0; col <= n; col++){
            if(row >= cost[0][0] && col >= cost[0][1]){ //当背包两种容量都超过当前的物品的体积时才能放入
                dp[row][col] = 1;        
            }else{          
                dp[row][col] = 0;
            }
        }
    }
    for(int layer = 1; layer < strsSize; layer++){  //layer即01背包中的物品
        for(int row = m; row >= 0; row--){    
            for(int col = n; col >= 0; col--){
                if(row>=cost[layer][0]&&col >= cost[layer][1]){ //防止索引出现负数报错
                    dp[row][col] = fmax(dp[row][col],dp[row-cost[layer][0]][col-cost[layer][1]]+1);
                }else{
                    dp[row][col] = dp[row][col];
                }
            }
        }
    }
    return dp[m][n];
}

2 零钱兑换 II

2.1 题目描述

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例1:

输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例2:

输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额 2 的硬币不能凑成总金额 3 。

示例3:

输入: amount = 10, coins = [10]
输出: 1

2.2 思路

  这一题与前边那些背包问题区别最大的是物品个数无限。当用滚动数组去求解时对背包容量进行遍历时不需要反过来遍历。

完整代码如下：

  • Cpp 实现
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        //未优化
        /*int dp[n][amount+1];
        memset(dp, 0, sizeof(dp));
        for(int c = 0; c <= amount; ++c){
            if(c % coins[0] == 0 || c == 0){
                dp[0][c] = 1;
            }
        }
        for(int r = 1; r < n; ++r){
            for(int c = 0; c <= amount; ++c){
                for(int k = 0; k <= c/coins[r]; ++k){
                    dp[r][c] += dp[r-1][c-k*coins[r]];
                }
            }
        }
        return dp[n-1][amount];*/
        //优化后
        int dp[amount+1];
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        for(int r = 0; r < n; ++r){
            for(int c = coins[r]; c <= amount; ++c){
                dp[c] += dp[c-coins[r]];
            }
        }
        return dp[amount];
    }
};
  • C 实现
int change(int amount, int* coins, int coinsSize){
    int dp[amount+1];
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for(int i = 0; i < coinsSize; i++){
        for(int j = coins[i]; j <= amount; j++){
            dp[j] += dp[j-coins[i]];
        }
    }
    return dp[amount];
}

3 组合总和 Ⅳ

3.1 题目描述

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例1:

输入: nums = [1,2,3], target = 4
输出: 7
解释:
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

示例2:

输入: nums = [9], target = 3
输出: 0

3.2 思路

  • 回溯：和其他组合问题一样，直接回溯非常简单，但会超时！

  • 动态规划：

完整代码如下：

  • Cpp 实现
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        int n = nums.size();
        int dp[target+1];
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        for(int c = 1; c <= target; ++c){
            for(int r = 0; r < n ; ++r){
                if(c >= nums[r] && dp[c-nums[r]] < INT_MAX-dp[c]){
                    dp[c] += dp[c - nums[r]];
                }
            }
        }
        return dp[target];
    }
};
  • C 实现
int combinationSum4(int* nums, int numsSize, int target){
    int dp[target+1];
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for(int i = 1; i <= target; i++){
        for(int j = 0; j < numsSize; j++){
            if(i - nums[j] >= 0 && dp[i-nums[j]] < INT_MAX-dp[i]){  
                dp[i] += dp[i-nums[j]];
            }
        }
    }
    return dp[target];
}

4 爬楼梯

4.1 题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例1:

输入: n =2
输出: 2
解释: 有两种方法可以爬到楼顶。

  1. 1 阶 + 1 阶
  2. 2 阶

示例2:

输入: n = 3
输出: 3
解释: 有三种方法可以爬到楼顶。

  1. 1 阶 + 1 阶 + 1 阶
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶

4.2 思路

简单题，没啥好写。

完整代码如下：

  • Cpp 实现
class Solution {
public:
    int climbStairs(int n) {
        if(n < 2) return n;
        int a = 1, b = 1, c;
        for(int i = 2; i <= n; ++i){
            c = b + a;
            a = b;
            b = c;
        }
        return c;
    }
};
  • C 实现
int climbStairs(int n){
    int dp[n+1];
    dp[0] = 1, dp[1] = 1;
    for(int i = 2; i <= n; i++){
        dp[i] = dp[i-1]+dp[i-2];
    }
    return dp[n];
}

5 零钱兑换

5.1 题目描述

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例1:

输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1

示例2:

输入: coins = [2], amount = 3
输出: -1

示例3:

输入: coins = [1], amount = 0
输出: 0

5.2 思路

  先创建一个dp数组，先用coins[0]去初始化dp数组，然后遍历整个coins数组。这里dp数组的含义是前i-1个硬币中构成当前整数的最少硬币数。设遍历coins数组的下标为i, 遍历amount的下标为j：

  • 当j < coins[i]时，当前硬币不可取，因此构成j的最少硬币数就等于前i-1构成j的最少硬币数，即dp[i][j] = dp[i-1][j].

  • 当j >= coins[i]时,说明当前的硬币可取：

    • 如果前i-1种硬币无法构成当前的j，即dp[i-1][j] == -1, 那么考虑取完当前的遍历到的硬币后，剩下部分是否能由前i种硬币构成，即检测dp[j-coins[i]]是否为-1，如果是，则说明前i种硬币无法构成j，因此置为-1；若否，则dp[i]应该更新为dp[j-coins[i]] + 1。
    • 如果dp[i-1][j] != -1则取原来的硬币数和[]dp[j-coins[i]] + 1中的较小值,即dp[i][j] = min(dp[i-1][j], dp[i][j - coins[i]]+1).

完整代码如下：

  • Cpp 实现
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        int dp[amount+1];
        for(int c = 0; c <= amount; ++c){
            if(c % coins[0] == 0){
                dp[c] = c/coins[0];
            }else{
                dp[c] = -1;
            }
        }
        if(n == 1){
            return dp[amount];
        }
        for(int r = 0; r < n; ++r){
            for(int c = 1; c <= amount; ++c){
                if(c >= coins[r] && dp[c-coins[r]] != -1){
                    if(dp[c] == -1){
                        dp[c]= dp[c-coins[r]]+1;
                    }else{
                        dp[c] = min(dp[c], dp[c-coins[r]]+1);
                    }
                }
            }
        }
        return dp[amount];
    }
};
  • C 实现
int coinChange(int* coins, int coinsSize, int amount){
    int n = coinsSize;
    int dp[amount+1];
    for(int i = 0; i <= amount; ++i){
        if(i == 0){
            dp[i] = 0;
            continue;
        }
        dp[i] = INT_MAX;
    }
    for(int r = 0; r < n; ++r){
        for(int c = 1;  c <= amount; ++c){
            if(c >= coins[r] && dp[c-coins[r]]!= INT_MAX){
                dp[c] = fmin(dp[c], dp[c-coins[r]]+1);
            }
        }
    }
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

6 完全平方数

6.1 题目描述

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例1:

输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4

示例2:

输入: n = 13
输出: 2
解释: 13 = 4 + 9

6.2 思路

  本题可以转化为背包容量为n，物品的质量依次为$1^2, 2^2, 3^2, …, (\sqrt{n})^2$,价值则均为1，目标是最小化价值的01背包问题。

完整代码如下：

  • Cpp 实现
class Solution {
public:
    int numSquares(int n) {
        int dp[n+1];
        dp[0] = 0;
        for(int i = 1; i <= n; i++){
            dp[i] = INT_MAX;
        }
        for(int i = 1; i*i <= n; ++i){  //物品
            for(int j = 1; j <= n; ++j){    //背包
                if(j >= i*i){
                    dp[j] = min(dp[j], dp[j - i*i]+1);
                }
            }
        }
        return dp[n];
    }
};
  • C 实现
int numSquares(int n){
    int dp[n+1];
    memset(dp, 1, sizeof(dp));
    for(int i = 1; i <= n; ++i){
        dp[i] = INT_MAX;
    }
    dp[0] = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j*j <= i; j++){
            dp[i] = fmin(dp[i], dp[i - j*j] + 1);
        }
    }
    return dp[n];
}

7 单词拆分

7.1 题目描述

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例1:

输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。

示例2:

输入: s = “applepenapple”, wordDict = [“apple”, “pen”]
输出: true
解释: 返回 true 因为 “applepenapple” 可以由 “apple” “pen” “apple” 拼接成。
注意，你可以重复使用字典中的单词。

示例3:

输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
输出: false

7.2 思路

  • 首先想到用字典树来解。

    1. 首先定义如下字典树结构体struct Tries：

      struct Tries{
    struct Tries *next[26];
    bool end = false;
    Tries() {        // 初始化
        is_end = false;
        memset(next, 0, sizeof(next));
    }
};

    2. 然后遍历整个wordDict，将所有的单词插入到字典树中。

    3. 创建一个栈用来存放字符串s中包含的wordDict完整单词的位置(结尾位置).当遇到结点的is_end为true,说明找到了一个完整单词，将当前的下标入栈。
    4. 当当前遍历到的字符在字典树中查找不到时，则将遍历位置更改为上一个完整单词的结尾在s中的位置，即出栈（这里有点贪心那味，优先遍历到叶节点），并从字典树根节点继续查找。

    5. 如果当前字符查找不到，且栈为空，则此时直接返回false。

      注意，当遍历完整个字符串时，当前结点的is_end为false时，此时不应该返回true，而应该重新继续查找，因为要完整的单词组成s。

      struct Tries{
    struct Tries *next[26];
    bool end = false;
    Tries() {        // 初始化
        end = false;
        memset(next, 0, sizeof(next));
    }
};

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        struct Tries *root = new Tries();
        //构建字典树
        struct Tries *cur;
        for(int i = 0; i < wordDict.size(); ++i){
            cur = root;
            for(char ch: wordDict[i]){
                int ptr = ch - 'a';
                if(cur->next[ptr] == nullptr){
                    cur->next[ptr] = new Tries();
                }
                cur = cur->next[ptr];
            }
            cur->end = true;
        }
        cur = root;
        stack<int> stk;
        for(int i = 0; i < s.length(); ++i){
            int ptr = s[i] - 'a';
            if(!cur || cur->next[ptr] == nullptr){
                if(stk.empty()){
                    return false;
                }else{
                    cur = root;
                    i = stk.top();
                    stk.pop();
                }
            }else{
                cur = cur->next[ptr];
                if(i == s.length()-1 && !cur->end){
                    cur = root;
                    i = stk.top();
                    stk.pop();
                }else if(cur->end){
                    stk.emplace(i);
                }
            }
        }
        return cur->end;
    }
};
      • 实际上，遇到下边算例时，上述代码将退化为暴力搜索，进而导致超时：
        ```["a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa","aaaaaaa", "aaaaaaaa", "aaaaaaaaa", "aaaaaaaaaa"]

    • 因此，需要引入“记忆化搜索”机制。增加一个布尔数组用于表示以某一位为查找起点会将会导致查找失败。具体的代码如下：

      struct Tries{
    struct Tries *next[26];
    bool end;
    Tries() {        // 初始化
        end = false;
        memset(next, 0, sizeof(next));
    }
};

class Solution {
    Tries* root;
    bool fail[301] = {0};
public:
    bool dfs(string& s, int startIndex){
        if(fail[startIndex] || startIndex == s.length()){
            if(fail[startIndex]) return false;
            return true;
        }
        struct Tries *cur = root;
        for(int i = startIndex; i < s.length(); ++i){
            int ptr = s[i] - 'a';
            if(cur->next[ptr]){
                cur = cur->next[ptr];
                if(cur->end && dfs(s, i+1)){
                    return true;
                }
            }else{
                break;
            }
        }
        fail[startIndex] = true;
        return false;
    }

    bool wordBreak(string s, vector<string>& wordDict) {
        root = new Tries();
        //构建字典树
        for(int i = 0; i < wordDict.size(); ++i){
            struct Tries *cur = root;
            for(char ch: wordDict[i]){
                int ptr = ch - 'a';
                if(cur->next[ptr] == nullptr){
                    cur->next[ptr] = new Tries();
                }
                cur = cur->next[ptr];
            }
            cur->end = true;
        }
        return dfs(s, 0);
    }
};

  • 动态规划

    • 首先创建一个set作为字典，将wordDict中的单词全部插入到其中。
    • 创建一个dp数组，表示前i位的子串是否能用字典中的单词来表示。遍历字符串，截取长度为j的子串，则有前i位是否能用字典中的单词来表示可以转换为前j位能否用字典中的单词来表示以及第j+1到i位(注意第j+1位下标对应j)的子串能否用字典中的单词来表示两个子问题，当且仅当两个子问题均为true，则该问题为true.

    • 前i位为dp[i]，则前j位为dp[j]、第j+1到i位的子串为s.substr(j, i-j),则状态转移方程位:

      其中$check(s[j…i-1])$表示子串$s[j…i-1]$是否存在字典中。

      优化：前边所述，j其实是从0开始，其实可以对这个地方进行优化，内循环中只要判断到最长单词的长度即可，即s[j...i-1]的长度至多为$max(s[i].length)$.

      优化后的完整代码如下：

      class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        //unordered_set<string> wordDictset(wordDict.begin(), wordDict.end());
        unordered_set<string> wordDictset;
        int maxlen = INT_MIN;
        for(auto word: wordDict){
            wordDictset.insert(word);
            maxlen = max(maxlen, (int)word.length());
        }
        int n =s.length();
        bool dp[n+1];
        memset(dp, false, sizeof(dp));
        dp[0] =true;
        for(int i = 1; i <= n; ++i){
            for(int j = i; j >= 0 && j >= i - maxlen; --j){
                if(dp[j] && wordDictset.count(s.substr(j, i-j))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};

8 打家劫舍

8.1 题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例1:

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

示例2:

输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

8.2 思路

  创建一个dp数组dp[n][2]，其含义为当前位取与不取的情况下的最大获利，其中第二维为0时不取，为1时则取。状态转移为当前位置取的条件是前一个位置不取，因此易得状态转移方程为:

完整代码如下：

  • Cpp 实现
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        /*
        int dp0 = 0, dp1 = 0;
        for(int i = 0; i < n; ++i){
            int new_dp0 = max(dp0, dp1);
            int new_dp1 = dp0 + nums[i];
            dp0 = new_dp0, dp1 = new_dp1;
        }
        return max(dp0, dp1);
        */
        int dp[n+1][2];
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= n; ++i){
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
            dp[i][1] = dp[i-1][0] + nums[i-1];
        }
        return max(dp[n][0], dp[n][1]);
    }
};
  • C 实现
int rob(int* nums, int numsSize){
    int dp[numsSize][2];
    dp[0][0] = 0;
    dp[0][1] = nums[0];
    for(int i = 1; i < numsSize; i++){
        dp[i][0] = fmax(dp[i-1][1], dp[i-1][0]);
        dp[i][1] = dp[i-1][0]+nums[i];
    }
    return fmax(dp[numsSize-1][0], dp[numsSize-1][1]);
}

9 打家劫舍 II

9.1 题目描述

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

示例1:

输入: nums = [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例2:

输入: nums = [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。

示例3:

输入: nums = [1,2,3]
输出: 3

9.2 思路

  数组围成一圈，而连续的两个位置不能同时取，因此，这一题比上一题多了一个约束，就是数组第一位和最后一位不能同时取。很明显，最重要的就是开头和结尾取不取，可以分为下面四种情况(下标从0开始)：

  1. 开头取：求[2, n-2]区间的最大值, 即0+[2， n-2]的最大值
  2. 开头不取：求[1, n-1]区间的最大值, 即[1， n-1]的最大值
  3. 结尾取：求[1, n-3]区间的最大值, 即(n-1) + [1， n-3]的最大值
  4. 结尾不取：求[0, n-2]区间的最大值, 即[0， n-2]的最大值

上边第1和第4其实可以变成求[0, n-2]区间的最大值，因为第1种相当于0取第4种对应0不取，而两者的区间的结尾都是n-2; 同理，第2和第3种可以转化为求[1, n-1]的最大值。

完整代码如下：

  • Cpp 实现
class Solution {
public:
    int myrob(vector<int> nums, int start, int end){
        int n = end - start + 1;
        int dp[n][2];
        dp[0][0] = 0, dp[0][1] = 0;
        for(int i = 1; i < n; ++i){
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
            dp[i][1] = dp[i-1][0] + nums[i-1+start];
        }
        return max(dp[n-1][0], dp[n-1][1]);
    }

    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n == 1) return nums[0];
        return max(myrob(nums, 0, n-1), myrob(nums, 1, n));
    }
};
  • C 实现
int rob(int* nums, int numsSize){
    if(numsSize == 1) return nums[0];
    
    int dp[numsSize][2], ans = 0;
    dp[0][0] = 0; dp[0][1] = nums[0];
    for(int i = 1; i < numsSize-1; i++){
        dp[i][0] = fmax(dp[i-1][1], dp[i-1][0]);
        dp[i][1] = dp[i-1][0]+nums[i];
    }
    ans = fmax(dp[numsSize-2][0], dp[numsSize-2][1]);
    dp[1][0] = 0; dp[1][1] = nums[1];
    for(int i =2; i<numsSize;i++){
        dp[i][0] = fmax(dp[i-1][1], dp[i-1][0]);
        dp[i][1] = dp[i-1][0]+nums[i];
    }
    ans = fmax(ans, fmax(dp[numsSize-1][0], dp[numsSize-1][1]));
    return ans;
}

10 打家劫舍 III

10.1 题目描述

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

示例1:

输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

示例2:

输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9

10.2 思路

  用 f(o) 表示选择 o 节点的情况下，o 节点的子树上被选择的节点的最大权值和；g(o) 表示不选择 o 节点的情况下，o 节点的子树上被选择的节点的最大权值和；l 和 r 代表 o 的左右孩子。

  • 当 o 被选中时，o 的左右孩子都不能被选中，故 o 被选中情况下子树上被选中点的最大权值和为 l 和 r 不被选中的最大权值和相加，即 f(o) = g(l) + g(r)。
  • 当 o 不被选中时，o 的左右孩子可以被选中，也可以不被选中。对于 o 的某个具体的孩子 x，它对 o 的贡献是 x 被选中和不被选中情况下权值和的较大值。故 g(o)=max{f(l),g(l)}+max{f(r),g(r)}。

完整代码如下：

  • Cpp 实现
class Solution {
public:
    int getMax(pair<int, int> a){
        return max(a.first, a.second);
    }
    pair<int, int> myRob(TreeNode* root){
        if(!root) return make_pair(0,0);

        auto left = myRob(root->left);
        auto right = myRob(root->right);
        int dp0 = getMax(left) + getMax(right);
        int dp1 = root->val + left.first + right.first;
        return make_pair(dp0, dp1);
    }
    int rob(TreeNode* root) {
        return getMax(myRob(root));
    }
};
  • C 实现
int getMax(int *a){
    return a[0] > a[1] ? a[0]:a[1];
}

int *myrob(struct TreeNode* root){
    int* ret = malloc(sizeof(int)*2);
    if(!root){
        ret[0] = 0, ret[1] = 0;
        return ret;
    };
    int *left = myrob(root->left);
    int *right = myrob(root->right);
    ret[0] = getMax(left) +getMax(right);
    ret[1] = root->val + left[0] + right[0];
    return ret;
}

int rob(struct TreeNode* root){
    return getMax(myrob(root));
}

总结

    1. 背包分类
    • 01背包：外循环物品（正序），内循环背包（倒序）
    • 完全背包：如若不考虑顺序问题，则无所谓先物品还是先背包，遍历顺序均为正序；若考虑顺序问题(即相同组成不同排列视为同一种)，则应当先遍历背包，后边遍历物品，而找零钱(相同组成不同排列视为多种)则应该先背包后物品。
    • 组合背包：如若不考虑顺序问题，则无所谓先物品还是先背包，遍历顺序均为正序；若考虑顺序问题，则应当先遍历背包，后边遍历物品。
    • 分组背包：外循环背包，内循环为上边三种背包之一
  • 问题分类：
    • 求最值：
      • 物品价值恒为1，常见于组成目标数的数字数量最少、找零钱使得零钱张数最少等，状态转移方程为：dp[i] = max/min(dp[i], dp[i-weight[j]]+1).
      • 物品价值为数组元素，常见于寻找数组中是否有子数列的加和/差等为目标值等，状态转移方程为：dp[i] = max/min(dp[i], dp[i-weight[j]]+val[j]).
    • 是否存在：
      • 常见于字符串匹配问题，状态转移方程为：dp[i] = dp[j]&&...或dp[i] = dp[i]||dp[i-weight[j]].
    • 组合问题：
      • 求构成目标的种类数量，状态转移方程为：dp[i] += dp[i-nums[j]].
    1. 树形DP
    • 树形DP实现时一般都是用子树更新父亲（即从下向上更新）
文章作者: Vyron Su
文章链接: http://example.com/2022/04/19/ch10-of-programmercarl-2/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Vyron Su !
C++ C 代码随想录 背包问题 动态规划