Dynamic planning for solving problems (4)

279. Complete square

summary ：

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

dp[j]： And for j The minimum number of complete squares of is dp[j]

2. Determine the recurrence formula 

dp[j] Can be dp[j - i * i] Introduction , dp[j - i * i] + 1 Then you can make dp[j].

At this point we have to choose the smallest dp[j], So the recurrence formula ：dp[j] = min(dp[j - i * i] + 1, dp[j]);

3.dp How to initialize an array 

dp[0] Express And for 0 The minimum number of perfect squares of , that dp[0] It must be 0.

There's a classmate problem , that 0 * 0 It's a kind of , Why? dp[0] Namely 0 Well ？

Look at the title , Find some perfect squares （ such as 1, 4, 9, 16, …）, The description of the title doesn't say to start from 0 Start ,dp[0]=0 It's all about recursion .

Not 0 Subscript dp[j] How much should it be ？

From recursive formula dp[j] = min(dp[j - i * i] + 1, dp[j]); You can see that every time dp[j] Choose the smallest , So not 0 Subscript dp[j] Be sure to start with the maximum value , such dp[j] It will not be covered by the initial value in recursion .

4. Determine the traversal order 

We know it's a complete backpack ,

If you find the combination number, it's the outer layer for Loop through items , Inner layer for Traverse the backpack .

dp[0] = 0 dp[1] = min(dp[0] + 1) = 1 dp[2] = min(dp[1] + 1) = 2 dp[3] = min(dp[2] + 1) = 3 dp[4] = min(dp[3] + 1, dp[0] + 1) = 1 dp[5] = min(dp[4] + 1, dp[1] + 1) = 2

error ：dp[i] = min(dp[i - j * j] + 1, dp[i]);

class Solution {
    
public:
    int numSquares(int n) {
    
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 0; i <= n; i++) {
     //  Traverse the backpack 
            for (int j = 1; j * j <= i; j++) {
     //  Traverse the items 
                dp[i] = min(dp[i - j * j] + 1, dp[i]);
            }
        }
        return dp[n];
    }
};

139. Word splitting

summary ：

substr() yes C++ Language functions , The main function is to copy substrings , It is required to start from the specified position , And has a specified length .

class Solution {
    
public:
    bool wordBreak(string s, vector<string>& wordDict) {
    
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        for (int i = 1; i <= s.size(); i++) {
       //  Traverse the backpack 
            for (int j = 0; j < i; j++) {
           //  Traverse the items 
                string word = s.substr(j, i - j); //substr( The starting position , The number of intercepts )
                if (wordSet.find(word) != wordSet.end() && dp[j]) {
    
                    dp[i] = true;
                }
            }
        }
        return dp[s.size()];
    }
};

198. raid homes and plunder houses

summary ：

dp[i]： Consider Subscripts i（ Include i） The houses within , The maximum amount that can be stolen is dp[i].

dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

   class Solution {
    
    public:
        int rob(vector<int>& nums) {
    
            if (nums.size() == 0) return 0;
            if (nums.size() == 1) return nums[0];
            vector<int> dp(nums.size());
            dp[0] = nums[0];
            dp[1] = max(nums[0], nums[1]);
            for (int i = 2; i < nums.size(); i++) {
    
                dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
            }
            return dp[nums.size() - 1];
        }
    };

213. raid homes and plunder houses II

summary ：

And case two and Situation three It includes case one , So just consider case 2 and case 3 .

As long as the individual problems are separated out , Compare them separately .\

error ： int result1 = robRange(nums, 0, nums.size() - 2);

		nums.size() - 1

i <= end; No i<end.

//  Pay attention to case 2 and case 3 in the notes , And the 198. The code of house raiding has been extracted 

class Solution {
    
public:
    int rob(vector<int>& nums) {
    
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];
        int result1 = robRange(nums, 0, nums.size() - 2); //  Situation two 
        int result2 = robRange(nums, 1, nums.size() - 1); //  Situation three 
        return max(result1, result2);
    }
    // 198. The logic of looting 
    int robRange(vector<int>& nums, int start, int end) {
    
        if (end == start) return nums[start];
        vector<int> dp(nums.size());
        dp[start] = nums[start];
        dp[start + 1] = max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
    
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[end];
    }
};

337. raid homes and plunder houses III

summary ： It's hard to understand .

1. Determine the parameters and return values of recursive functions

Here we require a node The money obtained by the two states of stealing and not stealing , Then the return value is a length of 2 Array of .

The parameter is the current node , The code is as follows ：

vector<int> robTree(TreeNode* cur) {

In fact, the return array here is dp Array .

therefore dp Array （dp table） And the meaning of subscripts ： Subscript to be 0 Record the maximum money obtained by not stealing the node , Subscript to be 1 Record the maximum money obtained by stealing the node .

So the topic. dp An array is an array with a length of 2 Array of ！

If it is stealing the current node , Then the left and right children can't steal ,val1 = cur->val + left[0] + right[0]; （ If you don't understand the meaning of subscript, just review dp The meaning of array ）

If you don't steal the current node , Then the left and right children can steal , As for whether to steal or not, we must choose the biggest , therefore ：val2 = max(left[0], left[1]) + max(right[0], right[1]);

Finally, the status of the current node is {val2, val1}; namely ：{ Do not steal the maximum money obtained by the current node , The maximum money obtained by stealing the current node }

error ： Return root node , Don't steal and steal

return {val2, val1};

class Solution {
    
public:
    int rob(TreeNode* root) {
    
        vector<int> result = robTree(root);
        return max(result[0], result[1]);
    }
    //  The length is 2 Array of ,0： Don't steal ,1： steal 
    vector<int> robTree(TreeNode* cur) {
    
        if (cur == NULL) return vector<int>{
    0, 0};
        vector<int> left = robTree(cur->left);
        vector<int> right = robTree(cur->right);
        //  steal cur
        int val1 = cur->val + left[0] + right[0];
        //  Don't steal cur
        int val2 = max(left[0], left[1]) + max(right[0], right[1]);
        return {
    val2, val1};
    }
};

• Time complexity ：O(n), Each node is traversed only once
• Spatial complexity ：O(\log n), Count the space of the recursive system stack