707 Design Linked List

错因：思考不完善，对于双链表，如何判断达到尾节点、插入索引的范围是多少（0到size都行）、删除索引的范围是多少（0到size-1）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
struct _node{
    int val;
    _node *prev;
    _node *next;
    _node(int val):val(val){};
};
class MyLinkedList {
private:
    _node *node;
    unsigned int size;
    _node* find_index(int index){
        _node *temp = node;
        for(int i = 0; i <= index; i++){
            temp = temp->next;
            if(temp == node && i != index) // 注意这里很关键
                return nullptr;
        }
        return temp;
    }
public:
    MyLinkedList(int val = -1) {
        node = new _node(val);
        node->prev = node;
        node->next = node;
        size = 0;
    }
    
    int get(int index) {
        _node *temp = node;
        for(int i = 0; i <= index; i++){
            temp = temp->next;
            if(temp == node)
                return -1;
        }
        return temp->val;
    }
    
    void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    void addAtTail(int val) {
        addAtIndex(size, val);
    }
    
    void addAtIndex(int index, int val) {
        auto temp = find_index(index);
        if(!temp)
            return;
        _node *data = new _node(val);
        temp->prev->next = data;
        data->prev = temp->prev;
        temp->prev = data;
        data->next = temp;
        size++;
    }
    void deleteAtIndex(int index) {
        if(index >= size)
            return;
        auto temp = find_index(index);
        if(!temp)
            return;
        auto prev = temp->prev;
        auto next = temp->next;
        prev->next = next;
        next->prev = prev;
        delete temp;
        size--;
    }
};

24 反转节点

错误原因：没有考虑尾端链表置空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* phead = new ListNode();
        ListNode* phead_cycle = phead;
        phead->next = head;
        ListNode* next;
        ListNode* thead = head;

        while(thead != nullptr && thead->next != nullptr){
            next = thead->next->next;
            phead_cycle->next = thead->next;
            phead_cycle->next->next = thead;
            phead_cycle = thead;
            thead = next;
        }
        phead_cycle->next = thead; // 没有这行就错了
        head = phead->next;
        //delete phead;[1,2,3,4]
        return head;
    }
};

19 移除元素

错误原因：思维不够缜密，比如mid == nullptr没判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        vector<ListNode*> vec;
        
        ListNode* hhead = new ListNode();
        ListNode* temp = hhead;
        hhead->next = head;
        if(!head)
            return head;
        
        while(temp->next != nullptr){
            vec.push_back(temp);
            temp = temp->next;
        }
        if(n > vec.size()){
            delete hhead;
            return head;
        }
        else{//主要是这里出错
            temp = vec[vec.size() - n];
            ListNode *mid = temp->next;
            if(mid == nullptr){
                temp->next = mid;
            }
            else{
                temp->next = mid->next;
                delete mid;
            }
                
            mid = hhead->next;
            delete hhead;
            return mid;
        }

    }
};

142 环形链表

主要思路是对的，但是为什么最后的while变成do while就不对了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(!head)
            return head;
        ListNode *fast = head, *low = head;

        do{
            if(fast->next != nullptr && fast->next->next != nullptr)
                fast = fast->next->next;
            else
                return nullptr;
            low = low->next;
        }
        while(low != fast);

        low = head;
        while(low != fast){   // 变成do while 就会错两个
            fast = fast->next;
            low = low->next;
        }
        ;
        return low;
    }
};

454

这题分为四个数，可以选择两两凑对，但错误点在于，两两之和没找全（第一个建立map的循环只写了一个）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        map<int, int> first, last;
        for(int i = 0; i < nums1.size(); i++){
            for(int j = 0; j < nums1.size(); j++){
                first[nums1[i] + nums2[j]]++;
                last[nums3[i] + nums4[j]]++;
            }
        }
        int counts = 0;
        map<int, int>::iterator temp;
        for(auto it : first){
            if(last.count(-it.first)){
                counts += it.second * last.find(-it.first)->second;
            }
        }
        return counts;
    }
};

三数之和

一个很大的问题在于超时，

  • 自己的思路是，先排序，再进行三层遍历+剪枝，超时。。。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    vector<vector<int>> threeSum(vector<int>& nums) {
            vector<vector<int>> out;
            int j = 0;
            sort(nums.begin(), nums.end());
            /*for(int i = 0; i < nums.size(); i++){
                if(nums[i+1] != nums[i])
                    nums[j++] = nums[i];
            }
            nums.erase(nums.begin()+j, nums.end());
            */
            
            for(int i = 0; i < nums.size(); i++){
                if(i > 0 && nums[i-1] == nums[i])
                    continue;
                for(int j = i+1; j < nums.size(); j++){
                    if(j >i+1 && nums[j] == nums[j-1])
                        continue;
                    if(nums[i]+nums[nums.size()-2]+nums[nums.size()-1] < 0)
                            break;
                    for(int k = j+1; k < nums.size(); k++){
                        if(k > j+1 && nums[k] == nums[k-1])
                            continue;
                        if(nums[i]+nums[j]+nums[nums.size()-1] < 0)
                            break;
                        if(nums[i]+nums[j]+nums[k] == 0 ){
                            out.push_back({nums[i],nums[j],nums[k]});
                        }
                        else if(nums[i]+nums[j]+nums[k] > 0){
                            break;
                        }
                    }
                }
            }
            return out;
        }

  • 双指针

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    class Solution {
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {
            vector<vector<int>> out;
            map<int, int> mmm;
            sort(nums.begin(), nums.end());
            for(int i = 0; i < nums.size()-2; i++){
                if(i > 0 && nums[i] == nums[i-1])   //去重
                    continue;
                int left = i+1, right = nums.size()-1;
                if(nums[i] > 0 || nums[right] < 0)
                    continue;
                while(left < right){
                    if(nums[i] + nums[left] + nums[right] == 0){
                        out.push_back({nums[i], nums[left], nums[right]});
                        left++;                                             //去重
                        while(left < nums.size() && nums[left] == nums[left-1])
                            left++;
                    }
                    else if(nums[i] + nums[left] + nums[right] < 0){
                        left++;
                        while(left < nums.size() && nums[left] == nums[left-1])
                            left++;
                    }
                    else{
                        right--;
                        while(right >= 0 && nums[right] == nums[right+1])
                            right--;
                    }
                        
                }
            }
            return out;
        }
    };

滑动窗口最大值239

要记录滑动窗口的最大值，只需要维护一个单调队列就行了，要动脑子想一下。

有点像kmp需要一个结构，来维护之前的信息，而更近的、更小的数据肯定是不需要的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class mycon{
public:
    deque<int> _data;
    void push(int item){
        while(!_data.empty() && item > _data.back()) _data.pop_back();
        _data.push_back(item);
    }
    void pop(int item){
        if(_data.front() == item){//如果item < front,那么该节点肯定没有被加入到deque中，不用管
            _data.pop_front();
        }
    }
    const int front(){return _data.front();};
};
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        /*vector<int> out;
        int max;
        for(int i = 0; i <= nums.size()-k; i++){
            max = nums[i];
            for(int j = i ; j < i+k; j++){
                max = max > nums[j] ? max:nums[j];
            }
            out.push_back(max);
        }
        return out;*/
        mycon con;
        vector<int> out;

        for(int i = 0; i < k; i++){
            con.push(nums[i]);
        }
        out.push_back(con.front());
        for(int i = k; i < nums.size(); i++){
            con.push(nums[i]);
            con.pop(nums[i-k]);
            out.push_back(con.front());
        }
        return out;
    }
};

前k个高频元素

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。首先可以通过一个map来统计，关键是如何根据值来排序，如果需要全排序，使用vector是可以的，但这里只需要找出k个最大的，用堆是最好的。优先级队列其实就是个堆。假设是n个数中找k个最大的数，

  • 如果用大顶堆，则需要构建容量为n的堆，然后pop出k个数
  • 如果用小顶堆，则需要构建容量为k的堆，堆中的数就是答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class compare{
public:
    bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs){
        return lhs.second > rhs.second;
    }
};
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> out;
        map<int, int> mmm;
        
        for(int i = 0; i < nums.size(); i++){
            mmm[nums[i]]++;
        }
        priority_queue<pair<int, int>, vector<pair<int, int>>, compare> com;
        for(const auto &item : mmm){
            com.push(item);
            if(com.size() > k)
                com.pop();
        }
        while(com.size()){
            auto temp = com.top();
            com.pop();
            out.push_back(temp.first);
        }
        return out;
    }
};

二叉树的迭代法遍历方式

二叉树使用栈很好遍历，使用迭代法时，前序很好处理，但后序和中序需要做点额外的处理。

用cur来访问左子节点，用栈来存储父节点.如果是后序，还需要一个变量来标识上一次访问的是左子节点还是右子节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        TreeNode* cur = root;
        vector<int> out;
        stack<TreeNode*> st;
        //用cur来访问左子节点，用栈来存储父节点
        while(nullptr != cur || !st.empty()){
            if(nullptr != cur){
                st.push(cur);
                cur = cur->left;
            }
            else{
                cur = st.top();
                st.pop();
                out.push_back(cur->val);
                cur = cur->right;
            }
        }
        return out;
    }
};

后序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
vector<int> postorderTraversal(TreeNode* root) {
    vector<int> out;
    TreeNode* cur = root, *last_visit = nullptr;
    stack<TreeNode*> st;
    while(nullptr != cur || !st.empty()){
        if(nullptr != cur){
            st.push(cur);
            cur = cur->left;
        }
        else{
            cur = st.top();
            if(cur->right && cur->right != last_visit){
                st.push(cur->right);
                cur = cur->right->left;
            }
            else{
                last_visit = cur;
                out.push_back(cur->val);
                st.pop();
                cur = nullptr; //这行很关键
            }
        }
    }
    return out;
}

迭代的统一版本：中序

可以使用加节点后加nullptr代表该节点的左子节点被访问了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
TreeNode* cur = root;
        vector<int> out;
        stack<TreeNode*> st;
        if(root) st.push(root);
        while(!st.empty()){
            cur = st.top();
            if(cur == nullptr){ //注意这里不能使用st.top() == nullptr, 而省略上面那行，会导致if内的cur没有被更新。
                st.pop();
                cur = st.top();
                st.pop();
                out.push_back(cur->val);
                if(cur->right) st.push(cur->right); //千万不能将空接点加进去了
            }
            else{ 
                
                st.push(nullptr);
                if(cur->left) st.push(cur->left);
            }
        }
        return out;
    }

迭代，后序（迭代法的巧妙点就在于用nullptr区分了已访问节点和未访问节点）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> out;
        TreeNode* cur = root;
        stack<TreeNode*> st;
        if(root) st.push(root);//避免将空接点加入
        while(!st.empty()){
            cur = st.top();
            if(nullptr != cur){
                st.push(nullptr);
                if(cur->right) st.push(cur->right);
                if(cur->left) st.push(cur->left);
            }
            else{
                st.pop();
                cur = st.top();
                st.pop();
                out.push_back(cur->val);
            }
        }
        return out;
    }
};

404左叶子节点

关键在于判断什么是左叶子节点：节点A的左孩子不为空，且左孩子的左右孩子都为空（说明是叶子节点），那么A节点的左孩子为左叶子节点（在父节点才能判断它的左子节点是不是左叶子节点，不能到子节点中判断，因为他可能没有父节点了）

1
2
3
4
5
6
7
int sumOfLeftLeaves(TreeNode* root) {
        int ret = 0;
        if(!root) return 0;//先序遍历，父节点，左子节点，右子节点
        if(root->left!=nullptr && root->left->left==nullptr && root->left->right==nullptr) 
            return root->left->val + sumOfLeftLeaves(root->right);
        return sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
    }

验证二叉搜索树

不能只判断左子节点小于父节点小于右子节点，要避免这种情况

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    long long prev = LONG_MIN;
    bool isValidBST(TreeNode* root) {
        if(!root) return true;
        bool left = isValidBST(root->left);
        if(prev >= root->val) return false;
        else prev = root->val;
        bool right = isValidBST(root->right);
        return left && right;
    }
};

450.

需要判断很多种情况，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        TreeNode* preroot = new TreeNode(INT_MIN);
        preroot->right = root;
        TreeNode* cur = preroot, *pre = nullptr;
        while(cur){
            if(cur->val == key){
                bool left;
                if(!pre->left) //错因1，没有判断pre->left 是否为空，而直接使用left = (pre->left->val == key)
                    left = false;
                else
                    left = (pre->left->val == key);
                std::cout << "dddd";
                if(!cur->left){
                    if(left) pre->left = cur->right;
                    else pre->right = cur->right;
                    std::cout << "jjjj";
                }
                else{
                    std::cout << "hhhh";
                    TreeNode* temp = cur->left;
                    if(temp->right == nullptr){
                        temp->right = cur->right;
                        if(left) pre->left = temp;
                        else pre->right = temp;
                        
                    }
                    else{
                        while(temp->right && temp->right->right != nullptr ) temp = temp->right;
                        if(left){
                            pre->left = temp->right;
                            temp->right = temp->right->left;
                            pre->left->left = cur->left;
                            pre->left->right = cur->right;
                        }
                        else{
                            pre->right = temp->right;
                            temp->right = temp->right->left;
                            pre->right->left = cur->left;
                            pre->right->right = cur->right;
                        }
                    }
                }
                delete cur;
                break;
            }
            else if(cur->val > key){
                pre = cur, cur = cur->left;
                std::cout << "left";
            }
            else{
                pre = cur, cur = cur->right;
                std::cout << "right";
            }
                
        }
        return preroot->right;
    }
};

17

组合优化中的问题，需要分为多阶段考虑，每阶段的结果是下一阶段的输出，要明确函数中需要做什么,比如这里就写错了，helper中只需要处理一个阶段，后面的阶段交给递归去解决所以不需要两个for循环。（这种问题太难debug了，这能读代码，分析）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    vector<vector<char>> map = {
        {'a', 'b', 'c'},
        {'d', 'e', 'f'},
        {'g', 'h', 'i'},
        {'j', 'k', 'l'},
        {'m', 'n', 'o'},
        {'p', 'q', 'r', 's'},
        {'t', 'u', 'v'},
        {'w', 'x', 'y', 'z'}};
    vector<string> res;
    void helper(string &path, int index, const string &digits){
        if(index == digits.size()){
            res.push_back(path);
            std::cout << index << endl;
            return;
        }
        for(int i = index; i < digits.size(); i++){
            std::cout << "i =" << i << endl;
            for(int j = 0; j < map[digits[i] - '2'].size(); j++){
                std::cout << "j =" << j << endl;
                path.push_back(map[digits[i] - '2'][j]);
                helper(path, i + 1, digits);
                path.pop_back();
            }
        }
    }
    vector<string> letterCombinations(string digits) {
        string path{};
        helper(path, 0, digits);
        return res;
    }
};

46.

注意for循环在使用了xxx.size等函数时，在循环内不能修改该对象：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> res;
    void helper(deque<int> nums, vector<int> &path){
        if(nums.empty()){
            res.push_back(path);
            return;
        }
        for(int i = 0; i < nums.size(); i++){
            auto temp = nums;
            std::cout << i << std::endl;
            path.push_back(nums[i]);
            temp.erase(temp.begin() + i);
            helper(temp, path);
            path.pop_back();
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        deque num(nums.begin(), nums.end());
        vector<int> path;
        helper(num, path);
        return res;
    }
};

47.

注意for循环使用的迭代器，那么在其中就不能更改容器里面的值了。

332.安排行程

有难度的，踩的几个坑，

  • 先把所有排列情况找出来，在在所有的情况中找出最靠前的，这个耗时太大了，不可取，
  • 然后是直接使用一阶段。想法是先将行程从小到大排序，因为递归时，是从1到n，前面的行程会先被访问，这样，只要找到了一种可行的行程，那么他就一定是最小的行程。
  • 这里需要不断递归，需要增删vector作为参数，要注意容器是否有效。

降低耗时采用的一些方式：

  • 传引用
  • 在for循环内层中，判断一下是否和上层循环的值一致，一致则continue继续循环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
vector<vector<string>> res;
    /*

    int findlow(vector<vector<string>> &total, vector<int> &vis, int index){
        string temp = total[vis[0]][index];
        for(auto i : vis){
            if(temp > total[i][index]){
                temp = total[i][index];
            }
        }
        vector<int> vis_p;
        //std::cout<<"[index"<<index<<"]:"<<temp << " is lower than ";
        for(auto i : vis){
            if(temp == total[i][index]){
                vis_p.push_back(i);
            }
            else{
                //std::cout << total[i][index] << ", ";
            }
        }
        std::cout << std::endl;
        if(vis_p.size() == 1 || index == total[0].size()-1){
            return vis_p[0];
        }
        else{
            return findlow(total, vis_p, index+1);
        }
        return 0;
    }*/
    bool helper(const vector<vector<string>>& tickets,vector<bool>& tmap, vector<string>& path){
        if(path.size() == tickets.size()+1){
            res.push_back(path);
            //std::cout << "\n";
            return true;
        }
        
            
        //std::cout << path.size() << std::endl;
        string pretemp = "";
        string target = path[path.size()-1];
        for(int i = 0; i < tickets.size(); i++){
            if(!tmap[i]  && tickets[i][0] == target && pretemp != tickets[i][1]){
                //std::cout << tickets[i][0] << "==" << target << std::endl;
                vector<string> temp = tickets[i];
                pretemp = temp[1];
                path.push_back(temp[1]);
                tmap[i] = true;
                //std::cout <<"<["<<i<<"/"<<ttickets.size()<<"]"<< temp[1];
                
                if(helper(tickets, tmap, path))
                    return true;
                path.pop_back();
                tmap[i] = false;
            }
            else{
                //std::cout << tickets[i][0] << "!=" << target << std::endl;
            }
        }
        return false;
    }

    vector<string> findItinerary(vector<vector<string>>& tickets) {
        vector<string> temp;
        temp.push_back("JFK");
        
        sort(tickets.begin(), tickets.end());
        vector<bool> tmap(tickets.size(), false);
        helper(tickets, tmap, temp);
        return res[0];
        /*vector<int> total;
        for(int i = 0; i < res.size(); i++){
            total.push_back(i);
        }
        int ret = findlow(res, total, 0);
        return res[ret];*/
    }
};

55.跳跃游戏

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

虽然这个题也可以使用dfs+递归来完成，但这明显效率太低，应该选择其他算法。动态规划中对应的多个阶段，如果每个阶段都选择最优的，那么其实就是贪心算法，如果每个阶段选择的由max{g(x1) + f(s-x1)}中选择最大的，则是动态规划。

134.加油站

主要思路是，因为题上说最多只有一种解法。想象一个数组sub = gas - cost。所以起点必然是出现在连续正数中的第一个正数的位置。

比如，sub = [-2, -2, 2, -1, 7, 8, -3]，那么起点必然是2或者7对应的索引值（2， 4）。因为只能有一个解法，如何连续正数的第二个位置可以循环一周，那么因为第一个位置是正数，那么第一个位置比如可以循环一周，与题冲突了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int total = 0;
        int index;
        int stacount = 0;
        for(int i = 0; i < gas.size()*2; i++){
            index = i % gas.size();
            total += gas[index] - cost[index];
            if(total >= 0){
                stacount++;
                if(stacount == gas.size()){
                    return (index+1)%gas.size();
                }
            }
            else{
                total = 0;
                stacount = 0;
            }
        }
        return -1;
    }
};

135.分发糖果

先初始化为1，分两个方向进行判断（第二次判断时需要用max取最大值）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int candy(vector<int>& ratings) {
    vector<int> data(ratings.size(), 1);
    for(int i = 1; i < ratings.size(); i++){
        if(ratings[i] > ratings[i-1])
            data[i] = data[i-1]+1;
    }
    for(int i = ratings.size()-2; i >= 0; i--){
        if(ratings[i] > ratings[i+1])
            data[i] = max(data[i+1]+1, data[i]);
    }
    int sum = 0;
    for(int i = 0; i < ratings.size(); i++){
        std::cout << data[i] << " ";
        sum += data[i];
    }
    return sum;
}

  1. 有空看看动态规划怎么做的吧

  2. 背包问题

    • 01背包
    • 多重背包（每种物品可以有无限个）：迭代公式dp[i][j] = max(dp[i-1][j], dp[i][j-data[i]])
      • 外层是遍历物品，内层遍历容量——物品是有顺序的，先第一个物品，后第二个物品（当我们计算的是达到给定价值的物品的种类时，dp中读出来的数量是一个组合数，如518. 零钱兑换 II - 力扣（LeetCode））
      • 物品是无序的，（当我们计算的是达到给定价值的物品的种类时，dp中读出来的数量是一个排列数，如377. 组合总和 Ⅳ - 力扣（LeetCode））

  3. 多重背包——组合求和

    基本如上所示，但是有一个细节dp[i][j] += dp[i-nums[j-1]][nums.size()];,其中nums.size()容易被写为j。整个式子的意思是，包含当前nums[j-1]的情况下的种类总数，但这对于之前的数的顺序是没有要求的，所以应该使用该行的最后一个数,