{"id":270,"date":"2026-03-24T11:04:05","date_gmt":"2026-03-24T03:04:05","guid":{"rendered":"http:\/\/47.110.38.12\/?p=270"},"modified":"2026-03-24T16:16:07","modified_gmt":"2026-03-24T08:16:07","slug":"day2","status":"publish","type":"post","link":"https:\/\/edryan.top\/index.php\/2026\/03\/24\/day2\/","title":{"rendered":"5\u5929\u901f\u6210\u6570\u636e\u7ed3\u6784\u4e0e\u7b97\u6cd5-Day2"},"content":{"rendered":"\n

5\u5929\u901f\u6210\u6570\u636e\u7ed3\u6784\u4e0e\u7b97\u6cd5-Day2<\/h1>\n\n\n\n

\u56fe\u8bba\u7b97\u6cd5<\/h2>\n\n\n\n

BFS<\/h3>\n\n\n\n

\u4ecb\u7ecd<\/h4>\n\n\n\n

\u5e7f\u5ea6\u4f18\u5148\u641c\u7d22(Breadth-First Search, BFS)\u662f\u4e00\u79cd\u56fe\u904d\u5386\u7b97\u6cd5\uff0c\u5b83\u4ece\u56fe\u7684\u67d0\u4e00\u9876\u70b9\u5f00\u59cb\uff0c\u5148\u8bbf\u95ee\u8be5\u9876\u70b9\u7684\u6240\u6709\u76f8\u90bb\u9876\u70b9\uff0c\u7136\u540e\u518d\u6309\u7167\u540c\u6837\u7684\u65b9\u5f0f\u8bbf\u95ee\u8fd9\u4e9b\u76f8\u90bb\u9876\u70b9\u7684\u76f8\u90bb\u9876\u70b9\uff0c\u5c42\u5c42\u63a8\u8fdb\uff0c\u76f4\u5230\u8bbf\u95ee\u5b8c\u56fe\u4e2d\u6240\u6709\u53ef\u8fbe\u9876\u70b9\u3002BFS\u7684\u7279\u70b9\u662f”\u5148\u8fdb\u5148\u51fa”\uff0c\u5373\u4f18\u5148\u8bbf\u95ee\u8ddd\u79bb\u8d77\u59cb\u9876\u70b9\u6700\u8fd1\u7684\u9876\u70b9\u3002<\/p>\n\n\n\n

\u7b97\u6cd5\u6b65\u9aa4<\/h4>\n\n\n\n
    \n
  1. \u9009\u62e9\u56fe\u4e2d\u7684\u4e00\u4e2a\u8d77\u59cb\u9876\u70b9\uff0c\u5c06\u5176\u6807\u8bb0\u4e3a\u5df2\u8bbf\u95ee\uff0c\u5e76\u653e\u5165\u961f\u5217\u4e2d<\/li>\n\n\n\n
  2. \u4ece\u961f\u5217\u4e2d\u53d6\u51fa\u961f\u9996\u9876\u70b9\uff0c\u8bbf\u95ee\u8be5\u9876\u70b9<\/li>\n\n\n\n
  3. \u5c06\u8be5\u9876\u70b9\u7684\u6240\u6709\u672a\u8bbf\u95ee\u8fc7\u7684\u76f8\u90bb\u9876\u70b9\u6807\u8bb0\u4e3a\u5df2\u8bbf\u95ee\uff0c\u5e76\u653e\u5165\u961f\u5217\u4e2d<\/li>\n\n\n\n
  4. \u91cd\u590d\u6b65\u9aa42\u548c3\uff0c\u76f4\u5230\u961f\u5217\u4e3a\u7a7a<\/li>\n<\/ol>\n\n\n\n

    \u7b97\u6cd5\u5b9e\u73b0<\/h4>\n\n\n\n
    #include <iostream>
    #include <unordered_map>
    #include <unordered_set>
    #include <vector>
    #include <queue>
    \u200b
    class BFSGraphTraversal {
    private:
        \/\/ \u90bb\u63a5\u8868\u8868\u793a\u7684\u56fe
        std::unordered_map<int, std::vector<int>> graph;
    \u200b
    public:
        \/\/ \u6dfb\u52a0\u9876\u70b9
        void addVertex(int vertex) {
            if (graph.find(vertex) == graph.end()) {
                graph[vertex] = std::vector<int>();
            }
        }
        
        \/\/ \u6dfb\u52a0\u8fb9
        void addEdge(int v1, int v2) {
            if (graph.find(v1) == graph.end()) {
                addVertex(v1);
            }
            if (graph.find(v2) == graph.end()) {
                addVertex(v2);
            }
            
            graph[v1].push_back(v2);
            \/\/ \u5bf9\u4e8e\u65e0\u5411\u56fe\uff0c\u9700\u8981\u6dfb\u52a0\u53cd\u5411\u8fb9
            \/\/ graph[v2].push_back(v1);
        }
        
        \/\/ BFS\u904d\u5386
        void bfs(int startVertex) {
            if (graph.find(startVertex) == graph.end()) {
                std::cout << \"\u8d77\u59cb\u9876\u70b9\u4e0d\u5b58\u5728\" << std::endl;
                return;
            }
            
            \/\/ \u8bb0\u5f55\u5df2\u8bbf\u95ee\u7684\u9876\u70b9
            std::unordered_set<int> visited;
            \/\/ \u961f\u5217\u7528\u4e8eBFS
            std::queue<int> queue;
            
            \/\/ \u5c06\u8d77\u59cb\u9876\u70b9\u6807\u8bb0\u4e3a\u5df2\u8bbf\u95ee\u5e76\u5165\u961f
            visited.insert(startVertex);
            queue.push(startVertex);
            
            while (!queue.empty()) {
                \/\/ \u51fa\u961f\u5e76\u8bbf\u95ee
                int currentVertex = queue.front();
                queue.pop();
                std::cout << currentVertex << \" \";
                
                \/\/ \u83b7\u53d6\u5f53\u524d\u9876\u70b9\u7684\u6240\u6709\u90bb\u63a5\u9876\u70b9
                std::vector<int> neighbors;
                if (graph.find(currentVertex) != graph.end()) {
                    neighbors = graph[currentVertex];
                }
                
                \/\/ \u5bf9\u6bcf\u4e2a\u672a\u8bbf\u95ee\u7684\u90bb\u63a5\u9876\u70b9\uff0c\u6807\u8bb0\u4e3a\u5df2\u8bbf\u95ee\u5e76\u5165\u961f
                for (int neighbor : neighbors) {
                    if (visited.find(neighbor) == visited.end()) {
                        visited.insert(neighbor);
                        queue.push(neighbor);
                    }
                }
            }
        }
    };<\/pre>\n\n\n\n
    Kruskal\u6700\u5c0f\u751f\u6210\u6811\u7b97\u6cd5<\/h3>\n\n\n\n
    \u4ecb\u7ecd<\/h4>\n\n\n\n
    Kruskal\u7b97\u6cd5\u662f\u4e00\u79cd\u7528\u4e8e\u5e26\u6743\u65e0\u5411\u56fe\u7684\u6700\u5c0f\u751f\u6210\u6811\u7b97\u6cd5\uff0c\u8be5\u7b97\u6cd5\u57fa\u4e8e\u8d2a\u5fc3\u7b56\u7565\uff0c\u901a\u8fc7\u9009\u62e9\u6743\u503c\u6700\u5c0f\u7684\u8fb9\u6784\u5efa\u6700\u5c0f\u751f\u6210\u6811\u3002<\/p>\n\n\n\n
    \u6700\u5c0f\u751f\u6210\u6811\u662f\u56fe\u4e2d\u8fde\u63a5\u6240\u6709\u9876\u70b9\u7684\u4e00\u4e2a\u5b50\u56fe\uff0c\u5b83\u662f\u4e00\u68f5\u6811\uff08\u65e0\u73af\u8fde\u901a\u56fe\uff09\uff0c\u4e14\u6240\u6709\u8fb9\u7684\u6743\u91cd\u603b\u548c\u6700\u5c0f\u3002<\/p>\n\n\n\n
    \u7b97\u6cd5\u6b65\u9aa4<\/h4>\n\n\n\n
      \n
    1. \u5c06\u56fe\u4e2d\u6240\u6709\u8fb9\u6309\u6743\u91cd\u4ece\u5c0f\u5230\u5927\u6392\u5e8f<\/li>\n\n\n\n
    2. \u521b\u5efa\u4e00\u4e2a\u68ee\u6797\uff08\u6bcf\u4e2a\u9876\u70b9\u521d\u59cb\u65f6\u662f\u4e00\u68f5\u72ec\u7acb\u7684\u6811\uff09<\/li>\n\n\n\n
    3. \u6309\u6392\u5e8f\u540e\u7684\u987a\u5e8f\u5904\u7406\u6bcf\u6761\u8fb9(u, v)\uff1a\n
        \n
      • \u5982\u679c\u9876\u70b9u\u548cv\u4e0d\u5728\u540c\u4e00\u4e2a\u8fde\u901a\u5206\u91cf\u4e2d\uff08\u5373\u4e0d\u5728\u540c\u4e00\u68f5\u6811\u4e2d\uff09<\/li>\n\n\n\n
      • \u5219\u5c06\u8fd9\u6761\u8fb9\u52a0\u5165\u6700\u5c0f\u751f\u6210\u6811\u4e2d<\/li>\n\n\n\n
      • \u5408\u5e76\u5305\u542bu\u548cv\u7684\u4e24\u68f5\u6811\uff08\u8fde\u901a\u5206\u91cf\uff09<\/li>\n<\/ul>\n<\/li>\n\n\n\n
      • \u91cd\u590d\u6b65\u9aa43\uff0c\u76f4\u5230\u6700\u5c0f\u751f\u6210\u6811\u5305\u542b\u56fe\u4e2d\u6240\u6709\u9876\u70b9\uff08\u5373V-1\u6761\u8fb9\uff0c\u5176\u4e2dV\u662f\u9876\u70b9\u6570\uff09<\/li>\n<\/ol>\n\n\n\n
        \u7b97\u6cd5\u8be6\u89e3<\/h4>\n\n\n\n
        \u4ee5\u5171\u67096\u4e2a\u9876\u70b9(A-F)\u548c10\u6761\u8fb9\u7684\u5e26\u6743\u65e0\u5411\u56fe\u4e3a\u4f8b\uff1a<\/p>\n\n\n\n
          \n
        • A-B\uff1a\u6743\u91cd3<\/li>\n\n\n\n
        • A-C\uff1a\u6743\u91cd1<\/li>\n\n\n\n
        • A-D\uff1a\u6743\u91cd6<\/li>\n\n\n\n
        • B-C\uff1a\u6743\u91cd5<\/li>\n\n\n\n
        • B-E\uff1a\u6743\u91cd4<\/li>\n\n\n\n
        • C-D\uff1a\u6743\u91cd5<\/li>\n\n\n\n
        • C-E\uff1a\u6743\u91cd6<\/li>\n\n\n\n
        • C-F\uff1a\u6743\u91cd4<\/li>\n\n\n\n
        • D-F\uff1a\u6743\u91cd2<\/li>\n\n\n\n
        • E-F\uff1a\u6743\u91cd6<\/li>\n<\/ul>\n\n\n\n
          \"img\"\/<\/div><\/figure>\n\n\n\n
          \u521d\u59cb\u5316\uff1a<\/h5>\n\n\n\n
            \n
          • \u6309\u6743\u91cd\u6392\u5e8f\u6240\u6709\u8fb9\uff1a\n
              \n
            1. A-C\uff1a\u6743\u91cd1<\/li>\n\n\n\n
            2. D-F\uff1a\u6743\u91cd2<\/li>\n\n\n\n
            3. A-B\uff1a\u6743\u91cd3<\/li>\n\n\n\n
            4. B-E\uff1a\u6743\u91cd4<\/li>\n\n\n\n
            5. C-F\uff1a\u6743\u91cd4<\/li>\n\n\n\n
            6. B-C\uff1a\u6743\u91cd5<\/li>\n\n\n\n
            7. C-D\uff1a\u6743\u91cd5<\/li>\n\n\n\n
            8. A-D\uff1a\u6743\u91cd6<\/li>\n\n\n\n
            9. C-E\uff1a\u6743\u91cd6<\/li>\n\n\n\n
            10. E-F\uff1a\u6743\u91cd6<\/li>\n<\/ol>\n<\/li>\n\n\n\n
            11. \u521d\u59cb\u68ee\u6797\uff1a\u6bcf\u4e2a\u9876\u70b9\u5404\u4e3a\u4e00\u68f5\u6811 {A}, {B}, {C}, {D}, {E}, {F}<\/li>\n<\/ul>\n\n\n\n
              \u6267\u884cKruskal\u7b97\u6cd5\uff1a<\/h5>\n\n\n\n
                \n
              1. \u5904\u7406\u8fb9A-C\uff08\u6743\u91cd1\uff09\uff1a\n
                  \n
                • A\u548cC\u4e0d\u5728\u540c\u4e00\u8fde\u901a\u5206\u91cf\u4e2d<\/li>\n\n\n\n
                • \u5c06\u8fb9A-C\u52a0\u5165\u6700\u5c0f\u751f\u6210\u6811<\/li>\n\n\n\n
                • \u5408\u5e76\u9876\u70b9A\u548cC\u7684\u8fde\u901a\u5206\u91cf: {A,C}, {B}, {D}, {E}, {F}<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                • \u5904\u7406\u8fb9D-F\uff08\u6743\u91cd2\uff09\uff1a\n
                    \n
                  • D\u548cF\u4e0d\u5728\u540c\u4e00\u8fde\u901a\u5206\u91cf\u4e2d<\/li>\n\n\n\n
                  • \u5c06\u8fb9D-F\u52a0\u5165\u6700\u5c0f\u751f\u6210\u6811<\/li>\n\n\n\n
                  • \u5408\u5e76\u9876\u70b9D\u548cF\u7684\u8fde\u901a\u5206\u91cf: {A,C}, {B}, {D,F}, {E}<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                  • \u5904\u7406\u8fb9A-B\uff08\u6743\u91cd3\uff09\uff1a\n
                      \n
                    • A\u548cB\u4e0d\u5728\u540c\u4e00\u8fde\u901a\u5206\u91cf\u4e2d<\/li>\n\n\n\n
                    • \u5c06\u8fb9A-B\u52a0\u5165\u6700\u5c0f\u751f\u6210\u6811<\/li>\n\n\n\n
                    • \u5408\u5e76\u9876\u70b9A\u548cB\u7684\u8fde\u901a\u5206\u91cf: {A,B,C}, {D,F}, {E}<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                    • \u5904\u7406\u8fb9B-E\uff08\u6743\u91cd4\uff09\uff1a\n
                        \n
                      • B\u548cE\u4e0d\u5728\u540c\u4e00\u8fde\u901a\u5206\u91cf\u4e2d<\/li>\n\n\n\n
                      • \u5c06\u8fb9B-E\u52a0\u5165\u6700\u5c0f\u751f\u6210\u6811<\/li>\n\n\n\n
                      • \u5408\u5e76\u9876\u70b9B\u548cE\u7684\u8fde\u901a\u5206\u91cf: {A,B,C,E}, {D,F}<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                      • \u5904\u7406\u8fb9C-F\uff08\u6743\u91cd4\uff09\uff1a\n
                          \n
                        • C\u548cF\u4e0d\u5728\u540c\u4e00\u8fde\u901a\u5206\u91cf\u4e2d<\/li>\n\n\n\n
                        • \u5c06\u8fb9C-F\u52a0\u5165\u6700\u5c0f\u751f\u6210\u6811<\/li>\n\n\n\n
                        • \u5408\u5e76\u9876\u70b9C\u548cF\u7684\u8fde\u901a\u5206\u91cf: {A,B,C,D,E,F}<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                        • \u6240\u6709\u9876\u70b9\u5df2\u7ecf\u5728\u540c\u4e00\u8fde\u901a\u5206\u91cf\u4e2d\uff0c\u7b97\u6cd5\u7ed3\u675f<\/li>\n<\/ol>\n\n\n\n
                          \u6211\u4eec\u5df2\u7ecf\u9009\u62e9\u4e865\u6761\u8fb9\uff08\u5bf9\u4e8e6\u4e2a\u9876\u70b9\u7684\u56fe\uff0c\u6700\u5c0f\u751f\u6210\u6811\u9700\u89815\u6761\u8fb9\uff09\uff0c\u56e0\u6b64\u4e0d\u518d\u5904\u7406\u5269\u4f59\u7684\u8fb9\uff1a<\/p>\n\n\n\n
                            \n
                          • B-C\uff08\u6743\u91cd5\uff09\uff1a\u4e0d\u5904\u7406<\/li>\n\n\n\n
                          • C-D\uff08\u6743\u91cd5\uff09\uff1a\u4e0d\u5904\u7406<\/li>\n\n\n\n
                          • A-D\uff08\u6743\u91cd6\uff09\uff1a\u4e0d\u5904\u7406<\/li>\n\n\n\n
                          • C-E\uff08\u6743\u91cd6\uff09\uff1a\u4e0d\u5904\u7406<\/li>\n\n\n\n
                          • E-F\uff08\u6743\u91cd6\uff09\uff1a\u4e0d\u5904\u7406<\/li>\n<\/ul>\n\n\n\n
                            \u6700\u7ec8\u7ed3\u679c\uff1a<\/h5>\n\n\n\n
                            \u6700\u5c0f\u751f\u6210\u6811\u5305\u542b\u4ee5\u4e0b\u8fb9\uff1a<\/p>\n\n\n\n
                              \n
                            • A-C\uff08\u6743\u91cd1\uff09<\/li>\n\n\n\n
                            • D-F\uff08\u6743\u91cd2\uff09<\/li>\n\n\n\n
                            • A-B\uff08\u6743\u91cd3\uff09<\/li>\n\n\n\n
                            • B-E\uff08\u6743\u91cd4\uff09<\/li>\n\n\n\n
                            • C-F\uff08\u6743\u91cd4\uff09<\/li>\n<\/ul>\n\n\n\n
                              \u603b\u6743\u91cd\uff1a1 + 2 + 3 + 4 + 4 = 14<\/p>\n\n\n\n
                              \u6838\u5fc3\u7279\u6027<\/h5>\n\n\n\n
                                \n
                              • \u8d2a\u5fc3\u7b56\u7565\uff1a\u6bcf\u6b21\u9009\u62e9\u6743\u91cd\u6700\u5c0f\u7684\u8fb9\uff0c\u53ea\u8981\u5b83\u4e0d\u4f1a\u5f62\u6210\u73af<\/li>\n\n\n\n
                              • \u5e76\u67e5\u96c6\uff1a\u4f7f\u7528\u5e76\u67e5\u96c6\u6570\u636e\u7ed3\u6784\u9ad8\u6548\u5b9e\u73b0\u8fde\u901a\u5206\u91cf\u7684\u7ba1\u7406\u548c\u5408\u5e76<\/li>\n\n\n\n
                              • \u6700\u4f18\u6027\uff1a\u4fdd\u8bc1\u5f97\u5230\u7684\u751f\u6210\u6811\u603b\u6743\u91cd\u6700\u5c0f<\/li>\n\n\n\n
                              • \u65f6\u95f4\u590d\u6742\u5ea6\uff1aO(E log E)\u6216O(E log V)\uff0c\u5176\u4e2dE\u4e3a\u8fb9\u6570\uff0cV\u4e3a\u9876\u70b9\u6570<\/li>\n\n\n\n
                              • \u7a7a\u95f4\u590d\u6742\u5ea6\uff1aO(E + V)\uff0c\u4e3b\u8981\u7528\u4e8e\u5b58\u50a8\u8fb9\u3001\u9876\u70b9\u548c\u5e76\u67e5\u96c6<\/li>\n<\/ul>\n\n\n\n
                                \u52a8\u6001\u89c4\u5212\uff08DP\uff09<\/h2>\n\n\n\n
                                \u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217LIS<\/h3>\n\n\n\n
                                \u4ecb\u7ecd<\/h4>\n\n\n\n
                                \u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217\uff08Longest Increasing Subsequence, LIS\uff09\u662f\u4e00\u4e2a\u7ecf\u5178\u7684\u52a8\u6001\u89c4\u5212\u95ee\u9898\uff0c\u76ee\u6807\u662f\u627e\u51fa\u4e00\u4e2a\u7ed9\u5b9a\u5e8f\u5217\u4e2d\u6700\u957f\u7684\u5b50\u5e8f\u5217\uff0c\u8981\u6c42\u8be5\u5b50\u5e8f\u5217\u4e2d\u7684\u6240\u6709\u5143\u7d20\u6309\u7167\u4e25\u683c\u9012\u589e\u7684\u987a\u5e8f\u6392\u5217<\/strong>\u3002\u6ce8\u610f\uff0c\u5b50\u5e8f\u5217\u4e0d\u8981\u6c42\u8fde\u7eed\uff0c\u4f46\u8981\u4fdd\u6301\u539f\u5e8f\u5217\u4e2d\u5143\u7d20\u7684\u76f8\u5bf9\u987a\u5e8f\u3002<\/p>\n\n\n\n
                                \u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217\u95ee\u9898\u53ef\u4ee5\u901a\u8fc7\u591a\u79cd\u65b9\u6cd5\u89e3\u51b3\uff0c\u5176\u4e2d\u52a8\u6001\u89c4\u5212\u662f\u6700\u4e3a\u7ecf\u5178\u548c\u76f4\u89c2\u7684\u65b9\u6cd5\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO(n\u00b2)\uff0cn\u662f\u5e8f\u5217\u957f\u5ea6\u3002\u8fd8\u6709\u4f7f\u7528\u4e8c\u5206\u67e5\u627e\u4f18\u5316\u7684\u65b9\u6cd5\u53ef\u4ee5\u5c06\u65f6\u95f4\u590d\u6742\u5ea6\u964d\u4f4e\u5230O(n log n)\u3002<\/p>\n\n\n\n
                                \u7b97\u6cd5\u6b65\u9aa4<\/h4>\n\n\n\n
                                  \n
                                1. \u5b9a\u4e49\u72b6\u6001\uff1adp[i]\u8868\u793a\u4ee5\u7b2ci\u4e2a\u5143\u7d20\u7ed3\u5c3e\u7684\u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217\u7684\u957f\u5ea6<\/li>\n\n\n\n
                                2. \u521d\u59cb\u5316\uff1a\u6240\u6709dp[i]\u521d\u59cb\u503c\u4e3a1\uff08\u81f3\u5c11\u5305\u542b\u81ea\u8eab\u4e00\u4e2a\u5143\u7d20\uff09<\/li>\n\n\n\n
                                3. \u72b6\u6001\u8f6c\u79fb\uff1a\u5bf9\u4e8e\u6bcf\u4e2a\u4f4d\u7f6ei\uff0c\u68c0\u67e5\u6240\u6709\u5728\u5b83\u4e4b\u524d\u7684\u4f4d\u7f6ej\uff1a\n
                                    \n
                                  • \u5982\u679cnums[i] > nums[j]\uff0c\u5219\u53ef\u4ee5\u5c06nums[i]\u63a5\u5728\u4ee5nums[j]\u7ed3\u5c3e\u7684\u5b50\u5e8f\u5217\u4e4b\u540e<\/li>\n\n\n\n
                                  • dp[i] = max(dp[i], dp[j] + 1)<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                                  • \u7ed3\u679c\uff1amax(dp[0], dp[1], …, dp[n-1])<\/li>\n<\/ol>\n\n\n\n
                                    \u7b97\u6cd5\u8be6\u89e3<\/h4>\n\n\n\n
                                    \u4e3a\u4e86\u66f4\u597d\u5730\u7406\u89e3\u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217\u7684\u52a8\u6001\u89c4\u5212\u6c42\u89e3\u8fc7\u7a0b\uff0c\u6211\u4eec\u4ee5\u5e8f\u5217 [10, 9, 2, 5, 3, 7, 101, 18] \u4e3a\u4f8b\uff0c\u8be6\u7ec6\u5206\u6790\u6574\u4e2a\u8ba1\u7b97\u6d41\u7a0b\uff1a<\/p>\n\n\n\n
                                    \u521d\u59cb\u5316\u9636\u6bb5<\/h5>\n\n\n\n
                                    \u521b\u5efa\u957f\u5ea6\u4e3a8\u7684dp\u6570\u7ec4\uff0c\u5e76\u5c06\u6240\u6709\u5143\u7d20\u521d\u59cb\u5316\u4e3a1\uff08\u8868\u793a\u6bcf\u4e2a\u5143\u7d20\u81ea\u8eab\u5c31\u662f\u4e00\u4e2a\u957f\u5ea6\u4e3a1\u7684\u9012\u589e\u5b50\u5e8f\u5217\uff09<\/p>\n\n\n\n
                                    dp = [1, 1, 1, 1, 1, 1, 1, 1]<\/pre>\n\n\n\n
                                    \u52a8\u6001\u89c4\u5212\u586b\u8868\u8fc7\u7a0b<\/h5>\n\n\n\n
                                    \u4ecei=1\u5f00\u59cb\uff0c\u5bf9\u6bcf\u4e2a\u4f4d\u7f6ei\u8fdb\u884c\u72b6\u6001\u8f6c\u79fb\uff1a<\/p>\n\n\n\n
                                      \n
                                    • i=1, nums[1]=9\uff1a\n
                                        \n
                                      • \u68c0\u67e5j=0, nums[0]=10\uff1a\u7531\u4e8e9<10\uff0c\u4e0d\u7b26\u5408\u9012\u589e\u6761\u4ef6<\/li>\n\n\n\n
                                      • dp[1]\u4fdd\u6301\u4e3a1<\/li>\n\n\n\n
                                      • \u5f53\u524ddp = [1, 1, 1, 1, 1, 1, 1, 1]<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                                      • i=2, nums[2]=2\uff1a\n
                                          \n
                                        • \u68c0\u67e5j=0, nums[0]=10\uff1a\u7531\u4e8e2<10\uff0c\u4e0d\u7b26\u5408\u9012\u589e\u6761\u4ef6<\/li>\n\n\n\n
                                        • \u68c0\u67e5j=1, nums[1]=9\uff1a\u7531\u4e8e2<9\uff0c\u4e0d\u7b26\u5408\u9012\u589e\u6761\u4ef6<\/li>\n\n\n\n
                                        • dp[2]\u4fdd\u6301\u4e3a1<\/li>\n\n\n\n
                                        • \u5f53\u524ddp = [1, 1, 1, 1, 1, 1, 1, 1]<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                                        • i=3, nums[3]=5\uff1a\n
                                            \n
                                          • \u68c0\u67e5j=0, nums[0]=10\uff1a\u7531\u4e8e5<10\uff0c\u4e0d\u7b26\u5408\u9012\u589e\u6761\u4ef6<\/li>\n\n\n\n
                                          • \u68c0\u67e5j=1, nums[1]=9\uff1a\u7531\u4e8e5<9\uff0c\u4e0d\u7b26\u5408\u9012\u589e\u6761\u4ef6<\/li>\n\n\n\n
                                          • \u68c0\u67e5j=2, nums[2]=2\uff1a\u7531\u4e8e5>2\uff0c\u7b26\u5408\u9012\u589e\u6761\u4ef6\uff0cdp[3]=max(dp[3], dp[2]+1)=max(1,2)=2<\/li>\n\n\n\n
                                          • dp[3]=2\uff0c\u8868\u793a\u4ee55\u7ed3\u5c3e\u7684LIS\u957f\u5ea6\u4e3a2<\/li>\n\n\n\n
                                          • \u5f53\u524ddp = [1, 1, 1, 2, 1, 1, 1, 1]<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                                          • i=4, nums[4]=3\uff1a\n
                                              \n
                                            • \u68c0\u67e5j=0,1,2,3\uff1a\u53ea\u6709\u5f53j=2\u65f6\uff0cnums[4]>nums[2]\uff083>2\uff09\uff0c\u66f4\u65b0dp[4]=2<\/li>\n\n\n\n
                                            • \u5f53\u524ddp = [1, 1, 1, 2, 2, 1, 1, 1]<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                                            • i=5, nums[5]=7\uff1a\n
                                                \n
                                              • \u68c0\u67e5j=0,1\uff1a\u4e0d\u7b26\u5408\u9012\u589e\u6761\u4ef6<\/li>\n\n\n\n
                                              • \u68c0\u67e5j=2\uff1a\u7531\u4e8e7>2\uff0c\u66f4\u65b0dp[5]=2<\/li>\n\n\n\n
                                              • \u68c0\u67e5j=3\uff1a\u7531\u4e8e7>5\uff0c\u66f4\u65b0dp[5]=max(dp[5], dp[3]+1)=max(2,3)=3<\/li>\n\n\n\n
                                              • \u68c0\u67e5j=4\uff1a\u7531\u4e8e7>3\uff0c\u66f4\u65b0dp[5]=max(dp[5], dp[4]+1)=max(3,3)=3<\/li>\n\n\n\n
                                              • \u5f53\u524ddp = [1, 1, 1, 2, 2, 3, 1, 1]<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                                              • i=6, nums[6]=101\uff1a\n
                                                  \n
                                                • \u5bf9\u4e8ej=0\u52305\uff0c\u6240\u6709\u5143\u7d20\u90fd\u5c0f\u4e8e101\uff0c\u627e\u51fa\u6700\u5927\u7684dp[j]+1<\/li>\n\n\n\n
                                                • \u6700\u5927\u7684dp[j]\u662fdp[5]=3\uff0c\u56e0\u6b64dp[6]=4<\/li>\n\n\n\n
                                                • \u5f53\u524ddp = [1, 1, 1, 2, 2, 3, 4, 1]<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                                                • i=7, nums[7]=18\uff1a\n
                                                    \n
                                                  • \u5bf9\u4e8ej=0\u52306\uff0c\u68c0\u67e5\u54ea\u4e9b\u5143\u7d20\u5c0f\u4e8e18<\/li>\n\n\n\n
                                                  • \u627e\u5230j=2,3,4,5\u65f6\u7b26\u5408\u6761\u4ef6\uff0c\u6700\u5927\u7684dp[j]\u662fdp[5]=3<\/li>\n\n\n\n
                                                  • \u66f4\u65b0dp[7]=dp[5]+1=4<\/li>\n\n\n\n
                                                  • \u6700\u7ec8dp = [1, 1, 1, 2, 2, 3, 4, 4]<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n
                                                    \u7ed3\u679c\u8ba1\u7b97<\/h5>\n\n\n\n
                                                      \n
                                                    1. dp\u6570\u7ec4\u4e2d\u7684\u6700\u5927\u503c\u5c31\u662f\u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217\u7684\u957f\u5ea6\uff1a<\/li>\n<\/ol>\n\n\n\n
                                                      \u6700\u5927\u503c = max(dp) = 4<\/pre>\n\n\n\n
                                                      \u627e\u51fa\u5177\u4f53\u7684\u5b50\u5e8f\u5217<\/h5>\n\n\n\n
                                                        \n
                                                      1. \u5982\u679c\u8981\u5f97\u5230\u5177\u4f53\u7684LIS\uff0c\u6211\u4eec\u9700\u8981\u56de\u6eaf\uff1a\n
                                                          \n
                                                        • \u4ecedp\u503c\u7b49\u4e8e\u6700\u5927\u957f\u5ea6\u7684\u4f4d\u7f6e\u5f00\u59cb\u8ffd\u8e2a<\/li>\n\n\n\n
                                                        • \u5728\u672c\u4f8b\u4e2d\uff0cdp[6]=dp[7]=4\uff0c\u6211\u4eec\u53ef\u4ee5\u4ece\u7d22\u5f157\uff08\u503c\u4e3a18\uff09\u5f00\u59cb<\/li>\n\n\n\n
                                                        • \u67e5\u627e\u7d22\u5f15j<7\uff0c\u4f7f\u5f97dp[j]=3\u4e14nums[j]<nums[7]\uff0c\u627e\u5230j=5\uff08\u503c\u4e3a7\uff09<\/li>\n\n\n\n
                                                        • \u7136\u540e\u67e5\u627e\u7d22\u5f15j<5\uff0c\u4f7f\u5f97dp[j]=2\u4e14nums[j]<nums[5]\uff0c\u627e\u5230j=3\uff08\u503c\u4e3a5\uff09<\/li>\n\n\n\n
                                                        • \u7ee7\u7eed\u67e5\u627e\u7d22\u5f15j<3\uff0c\u4f7f\u5f97dp[j]=1\u4e14nums[j]<nums[3]\uff0c\u627e\u5230j=2\uff08\u503c\u4e3a2\uff09<\/li>\n\n\n\n
                                                        • \u6700\u7ec8\u5f97\u5230LIS\u4e3a[2,5,7,18]<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n
                                                          \u56fe\u793a\u6f14\u793a<\/h5>\n\n\n\n
                                                          \u4e0b\u9762\u662f\u5404\u6b65\u9aa4\u7684dp\u6570\u7ec4\u53d8\u5316\u8fc7\u7a0b\u7684\u793a\u610f\u56fe\uff1a<\/p>\n\n\n\n
                                                          \u7d22\u5f15 i<\/th>0<\/th>1<\/th>2<\/th>3<\/th>4<\/th>5<\/th>6<\/th>7<\/th><\/tr><\/thead>
                                                          nums[i]<\/td>10<\/td>9<\/td>2<\/td>5<\/td>3<\/td>7<\/td>101<\/td>18<\/td><\/tr>
                                                          \u521d\u59cbdp<\/td>1<\/td>1<\/td>1<\/td>1<\/td>1<\/td>1<\/td>1<\/td>1<\/td><\/tr>
                                                          i=1\u540e<\/td>1<\/td>1<\/td>1<\/td>1<\/td>1<\/td>1<\/td>1<\/td>1<\/td><\/tr>
                                                          i=2\u540e<\/td>1<\/td>1<\/td>1<\/td>1<\/td>1<\/td>1<\/td>1<\/td>1<\/td><\/tr>
                                                          i=3\u540e<\/td>1<\/td>1<\/td>1<\/td>2<\/td>1<\/td>1<\/td>1<\/td>1<\/td><\/tr>
                                                          i=4\u540e<\/td>1<\/td>1<\/td>1<\/td>2<\/td>2<\/td>1<\/td>1<\/td>1<\/td><\/tr>
                                                          i=5\u540e<\/td>1<\/td>1<\/td>1<\/td>2<\/td>2<\/td>3<\/td>1<\/td>1<\/td><\/tr>
                                                          i=6\u540e<\/td>1<\/td>1<\/td>1<\/td>2<\/td>2<\/td>3<\/td>4<\/td>1<\/td><\/tr>
                                                          i=7\u540e<\/td>1<\/td>1<\/td>1<\/td>2<\/td>2<\/td>3<\/td>4<\/td>4<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
                                                          \u6838\u5fc3\u7279\u6027<\/h5>\n\n\n\n
                                                            \n
                                                          • \u5b50\u7ed3\u6784\u6700\u4f18\u6027<\/strong>\uff1a\u95ee\u9898\u7684\u6700\u4f18\u89e3\u5305\u542b\u5b50\u95ee\u9898\u7684\u6700\u4f18\u89e3<\/li>\n\n\n\n
                                                          • \u72b6\u6001\u5b9a\u4e49\u660e\u786e<\/strong>\uff1adp[i]\u8868\u793a\u4ee5\u7b2ci\u4e2a\u5143\u7d20\u7ed3\u5c3e\u7684LIS\u957f\u5ea6<\/li>\n\n\n\n
                                                          • \u65f6\u95f4\u590d\u6742\u5ea6<\/strong>\uff1a\u57fa\u672c\u5b9e\u73b0O(n\u00b2)\uff0c\u4f18\u5316\u7248\u672cO(n log n)<\/li>\n\n\n\n
                                                          • \u7a7a\u95f4\u590d\u6742\u5ea6<\/strong>\uff1aO(n)\uff0c\u9700\u8981\u4e00\u7ef4dp\u6570\u7ec4<\/li>\n\n\n\n
                                                          • \u975e\u8fde\u7eed\u6027<\/strong>\uff1a\u5b50\u5e8f\u5217\u5143\u7d20\u5728\u539f\u5e8f\u5217\u4e2d\u4e0d\u8981\u6c42\u8fde\u7eed<\/li>\n<\/ul>\n\n\n\n
                                                            \u57fa\u7840\u5b9e\u73b0<\/h4>\n\n\n\n
                                                            #include <iostream>
                                                            #include <vector>
                                                            #include <algorithm>
                                                            using namespace std;
                                                            \u200b
                                                            class LongestIncreasingSubsequence {
                                                            public:
                                                                int lengthOfLIS(vector<int>& nums) {
                                                                    if (nums.empty()) {
                                                                        return 0;
                                                                    }
                                                                    
                                                                    int n = nums.size();
                                                                    vector<int> dp(n, 1); \/\/ \u521d\u59cb\u5316\u6bcf\u4e2a\u4f4d\u7f6e\u7684LIS\u957f\u5ea6\u4e3a1
                                                                    
                                                                    int maxLength = 1;
                                                                    
                                                                    \/\/ \u52a8\u6001\u89c4\u5212\u8fc7\u7a0b
                                                                    for (int i = 1; i < n; i++) {
                                                                        for (int j = 0; j < i; j++) {
                                                                            if (nums[i] > nums[j]) {
                                                                                dp[i] = max(dp[i], dp[j] + 1);
                                                                            }
                                                                        }
                                                                        maxLength = max(maxLength, dp[i]);
                                                                    }
                                                                    
                                                                    return maxLength;
                                                                }
                                                                
                                                                vector<int> getLIS(vector<int>& nums) {
                                                                    if (nums.empty()) {
                                                                        return {};
                                                                    }
                                                                    
                                                                    int n = nums.size();
                                                                    vector<int> dp(n, 1);
                                                                    vector<int> prev(n, -1); \/\/ \u8bb0\u5f55\u524d\u9a71\u8282\u70b9
                                                                    
                                                                    int maxLength = 1;
                                                                    int endIndex = 0;
                                                                    
                                                                    \/\/ \u52a8\u6001\u89c4\u5212\u8fc7\u7a0b
                                                                    for (int i = 1; i < n; i++) {
                                                                        for (int j = 0; j < i; j++) {
                                                                            if (nums[i] > nums[j] && dp[j] + 1 > dp[i]) {
                                                                                dp[i] = dp[j] + 1;
                                                                                prev[i] = j; \/\/ \u8bb0\u5f55\u524d\u9a71
                                                                            }
                                                                        }
                                                                        if (dp[i] > maxLength) {
                                                                            maxLength = dp[i];
                                                                            endIndex = i; \/\/ \u8bb0\u5f55\u6700\u957f\u5b50\u5e8f\u5217\u7684\u7ed3\u675f\u4f4d\u7f6e
                                                                        }
                                                                    }
                                                                    
                                                                    \/\/ \u6839\u636e\u524d\u9a71\u6570\u7ec4\u6784\u9020LIS
                                                                    vector<int> lis;
                                                                    while (endIndex != -1) {
                                                                        lis.push_back(nums[endIndex]);
                                                                        endIndex = prev[endIndex];
                                                                    }
                                                                    
                                                                    reverse(lis.begin(), lis.end()); \/\/ \u9700\u8981\u53cd\u8f6c
                                                                    
                                                                    return lis;
                                                                }
                                                            };
                                                            \u200b
                                                            int main() {
                                                                vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
                                                                
                                                                LongestIncreasingSubsequence solution;
                                                                int lisLength = solution.lengthOfLIS(nums);
                                                                vector<int> lis = solution.getLIS(nums);
                                                                
                                                                cout << \"\u6570\u7ec4: \";
                                                                for (int num : nums) {
                                                                    cout << num << \" \";
                                                                }
                                                                cout << endl;
                                                                
                                                                cout << \"\u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217\u7684\u957f\u5ea6: \" << lisLength << endl;
                                                                
                                                                cout << \"\u4e00\u4e2a\u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217: \";
                                                                for (int num : lis) {
                                                                    cout << num << \" \";
                                                                }
                                                                cout << endl;
                                                                
                                                                return 0;
                                                            }
                                                            \u200b<\/pre>\n","protected":false},"excerpt":{"rendered":"
                                                            5\u5929\u901f\u6210\u6570\u636e\u7ed3\u6784\u4e0e\u7b97\u6cd5-Day2 \u56fe\u8bba\u7b97\u6cd5 BFS \u4ecb\u7ecd \u5e7f\u5ea6\u4f18\u5148\u641c\u7d22(Breadth-First Searc […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[14,15],"tags":[],"class_list":["post-270","post","type-post","status-publish","format-standard","hentry","category-14","category-15"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/edryan.top\/index.php\/wp-json\/wp\/v2\/posts\/270","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/edryan.top\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/edryan.top\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/edryan.top\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/edryan.top\/index.php\/wp-json\/wp\/v2\/comments?post=270"}],"version-history":[{"count":2,"href":"https:\/\/edryan.top\/index.php\/wp-json\/wp\/v2\/posts\/270\/revisions"}],"predecessor-version":[{"id":272,"href":"https:\/\/edryan.top\/index.php\/wp-json\/wp\/v2\/posts\/270\/revisions\/272"}],"wp:attachment":[{"href":"https:\/\/edryan.top\/index.php\/wp-json\/wp\/v2\/media?parent=270"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/edryan.top\/index.php\/wp-json\/wp\/v2\/categories?post=270"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/edryan.top\/index.php\/wp-json\/wp\/v2\/tags?post=270"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}