C++ 全栈知识体系

DP (Dynamic Programming)

从Search到DP，DP知识Seach上做一些优化与改进

当一个大问题是由多个子问题构成时，我们可以通过不断分解问题来最终构建我们相求的大问题。这个过程称为搜索(Search)。

搜索空间(Search Space)可以用Tree的形式展现出来，便于理解。

时间复杂度取决于这棵树的深度和每个node的children个数。

Search最重要的就是定义好状态，保证每个子问题都能用一个状态来描述。

Top Down DFS模板

Top Down DFS模板

  1. Define State of subproblems
  2. Initialize initial state
  3. Call dfs(init_state)

dfs(state)

  1. Base Case Check
  2. For each subproblem x a. update state = next_state_x b. branch down ——> call dfs(next_state_x) c. restore state

实践应用

78. 子集

子集

对于本题而言：

dfs(state)

  1. Base Case Check

  2. For each subproblem x a. update state = next_state_x

    1. (pos+1,subset)
    2. (pos+1,subset+nums[pos]) b. branch down ——> call dfs(next_state_x) c. restore state

以下为解题代码：

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> cur;
        int n=nums.size();
        dfs(n,0,cur,nums,res);

        return res;
    }

    void dfs(int n,int pos,vector<int> cur,vector<int>& nums,vector<vector<int>>& res){
        if(pos==n){
            res.push_back(cur);
            return;
        }

        cur.push_back(nums[pos]);
        dfs(n,pos+1,cur,nums,res);
        cur.pop_back();
        dfs(n,pos+1,cur,nums,res);

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Dynamic Programming

如果我们Search Space有重复子问题的话，可以记录下这些子问题的答案来保证不会重复计算多次。所以DP也称为Search + Memoization

时间复杂度取决于子问题的个数。

搜索空间(Search Space)可以用Tree的形式展现出来，便于理解。

所有DP都可以写成Bottom Up DFS 的形式。

重点仍然是定义好状态，定义好状态后，可以从一个中间状态出发思考递归规则。

Bottom Down DFS模板

Bottom Down DFS模板

  1. Define State of subproblems
  2. Initialize memo to record calculated subproblems
  3. retun dfs(top_level_answer_state)

dfs(state)

  1. Base Case Check

  2. If current problem is calculated , return its answer

  3. For each subproblem x

    a. Ask subprobelm for their answers ——> call dfs(subproblem_state) b. Build up current state problem answer based on subproblem answers

  4. Store current problem answer

实践应用

139. 单词拆分

单词拆分

以下为解题代码：
1

2D Dynamic Programming

  • 2D Array ——> state = (row,col)
  • 2 1D Array ——> Each 1D state
  • 1D Array + K ——> state = (i,k)
  • 1D Array ——> 2D statr (subarray)

← 堆 Heap →