DP Problemss I've met

Posted on

DP Problemss I've met

LC22

Note: BFS-Like Solution 

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 Solution
{
public:
    vector<string> generateParenthesis(int n)
    {
        deque<pair<string, pair<int, int>>> dq;
        vector<string> res;
        dq.push_back({"(", {1, 0}});
        while (!dq.empty())
        {
            auto tt = dq.front();
            string t = tt.first;
            auto l = tt.second.first, r = tt.second.second;
            dq.pop_front();

            if (t.length() == n * 2)
                res.push_back(t);
            else
            {
                if (l < n)
                    dq.push_back({t + "(", {l + 1, r}});

                if (r < l)
                    dq.push_back({t + ")", {l, r + 1}});
            }
        }
        return res;
    }
};