Dynamic programming for solving problems (2)

343. integer partition

1. determine dp Array （dp table） And the meaning of subscripts

dp[i]： Split numbers i, The maximum product that can be obtained is dp[i].

dp[i] The definition of is to carry out the whole problem-solving process , Which of the following steps I don't understand , Just think about it dp[i] What exactly does it mean ！

The recursive formula ：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));

You can understand that ,j * (i - j) It is simply to divide an integer into two numbers and multiply them , and j * dp[i - j] It is divided into two or more numbers and multiplied by .

class Solution {
    
public:
    int integerBreak(int n) {
    
        vector<int> dp(n + 1);
        dp[2] = 1;
        for (int i = 3; i <= n ; i++) {
    
            for (int j = 1; j < i - 1; j++) {
    
                dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
            }
        }
        return dp[n];
    }
};

96. Different binary search trees

dp[i] ： 1 To i The number of binary search trees composed of nodes is dp[i].

It can also be understood that i The number of binary search trees composed of different element nodes is dp[i] , It's all the same .

p[i] += dp[j - 1] * dp[i - j]; ,j-1 by j Is the number of nodes in the left subtree of the head node ,i-j For j Is the number of nodes in the right subtree of the head node

summary ：j <= i

class Solution {
    
public:
    int numTrees(int n) {
    
        vector<int> dp(n + 1);
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
    
            for (int j = 1; j <= i; j++) {
    
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
};

01 knapsack problem

namely dp[i] [j] Indicates from subscript [0-i] Take whatever you want from your belongings , Put in capacity j The backpack , What is the maximum total value .

/ weight Size of array   Is the number of items 
for(int i = 1; i < weight.size(); i++) {
     //  Traverse the items 
    for(int j = 0; j <= bagweight; j++) {
     //  Traverse the backpack capacity 
        if (j < weight[i]) dp[i][j] = dp[i - 1][j]; 
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

    }
}

void test_2_wei_bag_problem1() {
    
    vector<int> weight = {
    1, 3, 4};
    vector<int> value = {
    15, 20, 30};
    int bagweight = 4;

    //  Two dimensional array 
    vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));

    //  initialization 
    for (int j = weight[0]; j <= bagweight; j++) {
    
        dp[0][j] = value[0];
    }

    // weight Size of array   Is the number of items 
    for(int i = 1; i < weight.size(); i++) {
     //  Traverse the items 
        for(int j = 0; j <= bagweight; j++) {
     //  Traverse the backpack capacity 
            if (j < weight[i]) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

        }
    }

    cout << dp[weight.size() - 1][bagweight] << endl;
}

int main() {
    
    test_2_wei_bag_problem1();
}

416. To divide into equal and subsets

1. determine dp The meaning of arrays and subscripts

01 In the backpack ,dp[j] Express ： Capacity of j The backpack , The value of the items carried can be up to dp[j].

Get to the point ,dp[j] Express The total capacity of the backpack is j, The maximum can be made up j The sum of the subsets of is dp[j].

1. Determine the recurrence formula

01 The recurrence formula of knapsack is ：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

This topic , It's equivalent to putting values in your backpack , So the object i The weight of is nums[i], Its value is also nums[i].

So the recurrence formula ：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

1. dp How to initialize an array

stay 01 knapsack , A one-dimensional dp How to initialize , Already said ,

from dp[j] By definition , First dp[0] It must be 0.

If the value given by the topic is a positive integer, then it is not 0 Subscripts are initialized to 0 That's all right. , If the title gives a negative value , So no 0 The subscript is initialized to negative infinity .

In this way, we can make dp The maximum value of array in the process of recursive formula , Instead of being overwritten by the initial value .

In this topic A non empty array containing only positive integers , So not 0 The subscript element is initialized to 0 That's all right. .

  class Solution {
    
    public:
        bool canPartition(vector<int>& nums) {
    
            int sum = 0;
    
            // dp[i] Medium i Indicates the total amount in the backpack 
            //  In the title ： No more than elements per array  100, The size of the array will not exceed  200
            //  The sum will not be greater than 20000, Backpacks only need half of them at most , therefore 10001 Just the size 
            vector<int> dp(10001, 0);
            for (int i = 0; i < nums.size(); i++) {
    
                sum += nums[i];
            }
            if (sum % 2 == 1) return false;
            int target = sum / 2;
    
            //  Start  01 knapsack 
            for(int i = 0; i < nums.size(); i++) {
    
                for(int j = target; j >= nums[i]; j--) {
     //  Each element must be non repeatable , So go from big to small 
                    dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
                }
            }
            //  The sum of the elements in the set can be made exactly target
            if (dp[target] == target) return true;
            return false;
        }
    };

1049. The weight of the last stone II

summary ： In the calculation target When ,target = sum / 2 Because it's rounding down , therefore sum - dp[target] Must be greater than or equal to dp[target] Of .

for(int i = 0; i < weight.size(); i++) {
     //  Traverse the items 
    for(int j = bagWeight; j >= weight[i]; j--) {
     //  Traverse the backpack capacity 
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

class Solution {
    
public:
    int lastStoneWeightII(vector<int>& stones) {
    
        vector<int> dp(15001, 0);
        int sum = 0;
        for (int i = 0; i < stones.size(); i++) sum += stones[i];
        int target = sum / 2;
        for (int i = 0; i < stones.size(); i++) {
     //  Traverse the items 
            for (int j = target; j >= stones[i]; j--) {
     //  Traverse the backpack 
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - dp[target] - dp[target];
    }
};

494. Objectives and

dp[j] Express ： fill j（ Include j） Such a large volume bag , Yes dp[j] Methods

dp[j] += dp[j - nums[i]]

class Solution {
    
public:
    int findTargetSumWays(vector<int>& nums, int S) {
    
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) sum += nums[i];
        if (abs(S) > sum) return 0; //  There is no solution at this time 
        if ((S + sum) % 2 == 1) return 0; //  There is no solution at this time 
        int bagSize = (S + sum) / 2;
        vector<int> dp(bagSize + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < nums.size(); i++) {
    
            for (int j = bagSize; j >= nums[i]; j--) {
    
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[bagSize];
    }
};

• Time complexity ：O(n × m),n Is a positive number ,m For Backpack Capacity
• Spatial complexity ：O(m),m For Backpack Capacity
  474. One and zero

class Solution {
    
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
    
        vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); //  Default initialization 0
        for (string str : strs) {
     //  Traverse the items 
            int oneNum = 0, zeroNum = 0;
            for (char c : str) {
    
                if (c == '0') zeroNum++;
                else oneNum++;
            }
            for (int i = m; i >= zeroNum; i--) {
     //  Traverse the backpack capacity and traverse from back to front ！
                for (int j = n; j >= oneNum; j--) {
    
                    dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                }
            }
        }
        return dp[m][n];
    }
};