跟着karl学算法

第4章链表

链表在C++中的定义方式：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

对于删除链表中的节点，对于C++，需要手动释放内存，避免内存泄漏。以下是删除链表节点的示例代码：

ListNode* deleteNode(ListNode* head, int val) {
    if (!head) return nullptr;
    if (head->val == val) {
        ListNode* temp = head;
        head = head->next;
        delete temp; // 释放内存
        return head;
    }
    ListNode* current = head;
    while (current->next && current->next->val != val) {
        current = current->next;
    }
    if (current->next) {
        ListNode* temp = current->next;
        current->next = current->next->next;
        delete temp; // 释放内存
    }
    return head;
}

对于删除头节点，有两种方式：

直接修改头指针，返回新的头节点。
设置虚拟头节点，返回虚拟头节点的下一个节点。

对于删除倒数第n个节点，可以使用双指针技巧，先让一个指针走n步，然后两个指针同时前进，直到第一个指针到达末尾，此时第二个指针指向的就是要删除的节点。这种快慢指针的技巧十分常见。

对于链表找环，可以使用快慢指针法，快指针每次走两步，慢指针每次走一步，如果链表有环，最终快慢指针会相遇。若要找到环的入口，由于两者步数相差1，所以让一个节点从起点，另一个节点从相遇点出发，每次都走一步，最终会在环的入口相遇。

第5章哈希表

对于哈希冲突，常用的解决方法有链地址法和开放地址法。链地址法是为每个哈希表的槽位维护一个链表，所有映射到同一槽位的元素都存储在该链表中。需要注意平衡链表的长度与哈希表的大小。开放地址法是在发生冲突时，寻找下一个空槽位存储元素。常用的探测方法有线性探测、二次探测和双重哈希。要求哈希表的大小大于元素个数，以减少冲突。

对于结构的实现，set是一种不允许重复元素的集合，底层通常使用红黑树实现，支持有序遍历。而unordered_set是一种不允许重复元素的集合，底层使用哈希表实现，不保证元素的顺序，但查找、插入和删除操作的平均时间复杂度为O(1)。相对应的，map是一种键值对集合，底层通常使用红黑树实现，支持有序遍历。而unordered_map是一种键值对集合，底层使用哈希表实现，不保证键值对的顺序，但查找、插入和删除操作的平均时间复杂度为O(1)。

例题：两个数组的交集

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    unordered_set<int> set1(nums1.begin(), nums1.end());
    unordered_set<int> resultSet;
    for (int num : nums2) { // 按值复制遍历nums2!
        if (set1.find(num) != set1.end()) { // 如果在set1中找到num
            resultSet.insert(num);
        }
    }
    return vector<int>(resultSet.begin(), resultSet.end());
}

例题：两数之和

vector<int> twoSum(vector<int>& nums, int target) {
    std::unordered_map<int, int> numMap; // 存储数值及其索引
    for (int i = 0; i < nums.size(); ++i) {
        auto iter = numMap.find(target - nums[i]);
        if (iter != numMap.end()) {
            return {iter->second, i}; // 找到目标值，返回索引
        }
        numMap.insert(pair<int, int>(nums[i], i)); // 插入当前数值及其索引
    }
    return {}; // 未找到，返回空向量
}

例题：三数之和（使用双指针法）：注意去重使用continue跳过

例题：四数之和--同样使用双指针法，外层两层循环固定前两个数，内层双指针寻找后两个数，注意去重。

    result.push_back(vector<int>{nums[i], nums[j], nums[left], nums[right]});

双指针用途：

降低一个数量级的时间复杂度，例如从O(n^2)降到O(n)。
使用双指针记录前后指针，反转链表。
快慢指针寻找链表中点，判断链表是否有环等。

第6章字符串

例题：反转字符串有库函数std::reverse，也可以使用双指针法，从字符串两端向中间移动，交换字符。 reverse(s.begin(), s.end());

例题：反转字符串中的单词先整体反转字符串，然后逐个反转每个单词，最后去除多余空格。如果使用s.erase()删除空格，注意erase会改变字符串长度，索引需要相应调整，会增加复杂度。因而，建议使用双指针法构建新的字符串，避免频繁删除操作，配合resize函数调整字符串大小。

s.resize(newLength);
return s;

KMP算法： next数组表示的是前缀表的变形，用于记录模式串中每个位置之前的子串的最长相等前后缀的长度。前缀表的任务是当前匹配失败时，告诉模式串应该跳到哪个位置继续匹配，从而避免重复比较已经匹配过的字符。通过将对应的最长后缀等效替换为前缀，可以实现模式串的跳跃式移动，提高匹配效率。 KMP算法的时间复杂度为O(n+m)，其中n是文本串长度，m是模式串长度。空间复杂度为O(m)，用于存储next数组。

无论是在计算next，还是在进行匹配的时候，j都从-1开始，表示当前没有匹配任何字符。

void computeNext(const string& pattern, vector<int>& next) {
    int m = pattern.size();
    next.resize(m);
    next[0] = -1; // 初始化第一个位置
    int j = -1; // j表示当前匹配的前缀长度
    for (int i = 1; i < m; ++i) {
        while (j >= 0 && pattern[i] != pattern[j + 1]) {
            j = next[j]; // 回溯到上一个匹配位置
        }
        if (pattern[i] == pattern[j + 1]) {
            ++j; // 匹配成功，前缀长度加1
        }
        next[i] = j; // 记录当前前缀长度
    }
}
int KMP(const string& text, const string& pattern) {
    int n = text.size();
    int m = pattern.size();
    if (m == 0) return 0; // 空模式串匹配成功，返回0
    vector<int> next;
    computeNext(pattern, next);
    int j = -1; // j表示当前匹配的前缀长度
    for (int i = 0; i < n; ++i) {
        while (j >= 0 && text[i] != pattern[j + 1]) {
            j = next[j]; // 回溯到上一个匹配位置
        }
        if (text[i] == pattern[j + 1]) {
            ++j; // 匹配成功，前缀长度加1
        }
        if (j == m - 1) {
            return i - m + 1; // 找到匹配，返回起始索引
        }
    }
    return -1; // 未找到匹配
}

第7章栈与队列

HP STL是C++ STL的第一个实现版本，包含了基本的容器和算法实现。 P.J. Plauger是HP STL的主要设计者和实现者，他在1994年发布了《C++ Standard Template Library》一书，详细介绍了STL的设计理念和实现细节，但不是开源的。 SGI STL是由Silicon Graphics公司开发的STL实现版本，于1996年开源发布，成为C++ STL的一个重要实现，对后续的STL发展产生了深远影响。

在SGL STL中，stack和queue都是适配器容器，默认情况下均使用deque作为底层容器。

std::stack<int> myStack; // 默认使用deque作为底层容器
std::stack<int, std::vector<int>> myStackVec; // 使用vector作为底层容器
std::queue<int> myQueue; // 默认使用deque作为底层容器
std::queue<int, std::list<int>> myQueueList; // 使用list作为底层容器

例题：用栈实现队列我们可以用两个栈来实现队列的功能。一个栈用于入队操作，另一个栈用于出队操作。当需要出队时，如果出队栈为空，则将入队栈中的所有元素弹出并压入出队栈，然后从出队栈弹出元素。

如果我们可以复用特定函数，则尽量不要将代码重复编写，避免冗余代码。

例题：用队列实现栈我们可以只使用一个队列来实现栈的功能。每次入栈时，将新元素加入队列，然后将队列中除新元素外的所有元素依次出队并重新入队，这样新元素就会位于队列的前端，实现了栈的后进先出特性。

例题：使用deque实现滑动窗口最大值

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq; // 存储元素索引的双端队列
    vector<int> result;
    for (int i = 0; i < nums.size(); ++i) {
        // 移除不在窗口范围内的元素
        if (!dq.empty() && dq.front() == i - k) {
            dq.pop_front();
        }
        // 移除所有小于当前元素的元素
        while (!dq.empty() && nums[dq.back()] < nums[i]) {
            dq.pop_back();
        }
        dq.push_back(i); // 将当前元素索引加入队列
        // 当窗口大小达到k时，记录当前最大值
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }
    return result;
}

例题：接雨水第一种方法是使用双指针法，从中间向两端扩展，计算每个位置的积水量。第二种方法是使用单调栈，遍历高度数组，维护一个单调递减的栈，当遇到比栈顶元素高的高度时，计算积水量，不需要储存pair。

int trap(vector<int>& height) {
    int n = height.size();
    if (n == 0) return 0;
    stack<int> st;
    int waterTrapped = 0;
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && height[i] > height[st.top()]) {
            int top = st.top();
            st.pop();
            if (st.empty()) break;
            int distance = i - st.top() - 1;
            int boundedHeight = min(height[i], height[st.top()]) - height[top];
            waterTrapped += distance * boundedHeight;
        }
        st.push(i);
    }
    return waterTrapped;
}

总而言之，默认情况下，栈与队列使用deque作为底层容器，这意味着其在内存中的存储是不连续的。当然，因为栈和队列是适配器容器，我们也可以选择其他底层容器，如vector或list，根据具体需求进行优化。

第8章二叉树

定义：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

平衡二叉搜索树（AVL树）是一种自平衡的二叉搜索树，确保在每次插入或删除节点后，树的高度差不超过1，从而保持O(log n)的时间复杂度进行查找、插入和删除操作。

二叉树的遍历方式： dfs包括前序、中序、后序遍历，通常使用递归实现，也可以使用栈实现非递归版本。

前序遍历：访问根节点 -> 遍历左子树 -> 遍历右子树
中序遍历：遍历左子树 -> 访问根节点 -> 遍历右子树
后序遍历：遍历左子树 -> 遍历右子树 -> 访问根节点 bfs即层序遍历，通常使用队列实现。
层序遍历：按层次从上到下、从左到右访问节点

使用递归遍历相对容易，只需要使用vector& result来存储结果。而使用迭代遍历时，需要使用栈或队列以及指针来辅助存储节点，模拟递归过程。

对于前序遍历，可以先将右子节点入栈，再将左子节点入栈，这样出栈时先访问左子节点，符合前序遍历顺序。

对于中序遍历，如同递归一样，先访问左子节点，然后访问根节点，最后访问右子节点。可以使用一个指针不断向左遍历，将节点入栈，直到左子节点为空，然后弹出栈顶节点访问，再将指针指向右子节点，继续上述过程。

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> st;
    TreeNode* current = root;
    while (current != nullptr || !st.empty()) {
        if (current != nullptr) {
            st.push(current);
            current = current->left;
        } else {
            current = st.top();
            st.pop();
            result.push_back(current->val);
            current = current->right;
        }
    }
    return result;
}

对于后序遍历，同前序遍历类似，可以先将左子节点入栈，再将右子节点入栈，这样出栈时先访问右子节点，符合后序遍历顺序。最后将结果反转即可。

如果我们想要将中序遍历同前序遍历与后序遍历一个模板，我们可以采用标记法，在中节点前插入一个空节点作为标记，表示该节点已经被访问过，下一次弹出时就可以访问该节点的值, 然后把这个值放到vector中。这样就可以统一处理三种遍历方式。

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> st;
    if (root) st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top();
        if (node) {
            st.pop();
            if (node->right) st.push(node->right);
            st.push(node); // 将当前节点再次入栈作为标记
            st.push(nullptr); // 标记当前节点已被访问
            if (node->left) st.push(node->left);
        } else {
            st.pop(); // 弹出标记
            node = st.top();
            st.pop();
            result.push_back(node->val); // 访问节点值
        }
    }
    return result;
}

例题：反转二叉树

TreeNode* invertTree(TreeNode* root) {
    if (!root) return nullptr;
    swap(root->left, root->right);
    invertTree(root->left);
    invertTree(root->right);
    return root;
}

例题：对称二叉树此题需要使用后序遍历，结合递归三部曲：确定递归函数的参数和返回值，确定终止条件，确定单层递归的逻辑。

bool isMirror(TreeNode* t1, TreeNode* t2) {
    if (!t1 && !t2) return true;
    if (!t1 || !t2) return false;
    return (t1->val == t2->val) &&
           isMirror(t1->left, t2->right) &&
           isMirror(t1->right, t2->left);
}

例题：所有路径使用to_string函数将整数转换为字符串，构建路径字符串时注意添加"->"分隔符，最后将路径字符串加入结果向量中。

void dfs(TreeNode* node, vector<int>& path, vector<string>& result) {//注意参数传递方式，path需要引用传递，result也需要引用传递
    if (!node) return;
    path.push_back(node->val);
    if (!node->left && !node->right) {
        // 到达叶子节点，构建路径字符串
        string pathStr;
        for (size_t i = 0; i < path.size(); ++i) {
            pathStr += to_string(path[i]);
            if (i < path.size() - 1) {
                pathStr += "->";
            }
        }
        result.push_back(pathStr);
    } else {
        dfs(node->left, path, result);
        dfs(node->right, path, result);
    }
    path.pop_back(); // 回溯
}

例题：中后序遍历构建二叉树思路：后序遍历是左右中顺序，中序遍历是左中右顺序，因此后序遍历的最后一个元素是树的根节点，在中序遍历中找到这个根节点的位置，就可以将中序遍历分为左子树和右子树两部分，然后递归构建左右子树。需要确定左闭右开的区间，且如果只有一个节点时，则说明子树只有一个节点，直接返回该节点即可。

同理，如果是前序遍历和中序遍历构建二叉树，则前序遍历的第一个元素是树的根节点，在中序遍历中找到这个根节点的位置，就可以将中序遍历分为左子树和右子树两部分，然后递归构建左右子树。然而如果提供了前序遍历和后序遍历，则无法唯一确定一棵二叉树，因为前序遍历和后序遍历都无法确定左右子树的边界，因此无法唯一确定树的结构。

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    if (inorder.empty() || postorder.empty()) return nullptr;
    int rootVal = postorder.back();
    TreeNode* root = new TreeNode(rootVal);
    auto it = find(inorder.begin(), inorder.end(), rootVal);
    int leftSize = distance(inorder.begin(), it);
    vector<int> leftInorder(inorder.begin(), it);
    vector<int> rightInorder(it + 1, inorder.end());
    vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftSize);
    vector<int> rightPostorder(postorder.begin() + leftSize, postorder.end() - 1);
    root->left = buildTree(leftInorder, leftPostorder);
    root->right = buildTree(rightInorder, rightPostorder);
    return root;
}

例题：判断二叉搜索树我们可以通过中序遍历二叉树，得到一个有序的序列，如果这个序列是严格递增的，那么说明这棵树是二叉搜索树。如果我们使用迭代，为了避免最小值初始化的问题，我们可以从树的最左下儿子节点开始遍历，记录前一个访问的节点值，如果当前访问的节点值不大于前一个访问的节点值，则说明不是二叉搜索树。

例题：二叉树的最近公共祖先我们可以使用递归来解决这个问题。对于每个节点，我们检查它是否是p或q，如果是，则返回该节点。然后我们递归检查左子树和右子树，如果左子树和右子树都返回非空值，说明当前节点就是最近公共祖先。如果只有一个子树返回非空值，则说明最近公共祖先在那个子树中。 `cpp TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (!root || root == p || root == q) return root; TreeNode* left = lowestCommonAncestor(root->left, p, q); TreeNode* right = lowestCommonAncestor(root->right, p, q); if (left && right) return root; // p和q分别在左右子树中 return left ? left : right; // 否则在左子树或右子树中 }

若为二叉搜索树，则可以利用其性质，比较当前节点值与p和q的值，来决定向左子树还是右子树递归，从而提高效率。

例题：在二叉树中删除节点删除节点时需要考虑三种情况：

删除的节点是叶子节点，直接删除即可。
删除的节点只有一个子节点，将该子节点替换删除节点的位置。
删除的节点有两个子节点，找到该节点的左子树放在右子树的最左下儿子节点的左子树上，然后将右子树替换删除节点的位置。

对于进阶版的修剪二叉树，要求删除所有不在范围 [low, high] 内的节点，原理类似，我们可以使用递归来实现，首先递归修剪左子树和右子树，然后根据当前节点的值与low和high的关系来决定是否删除当前节点以及如何连接修剪后的子树。

总而言之，针对二叉树，我们需要考虑三种遍历方式各自的适用范围。针对二叉树的构造，前序遍历可以保证先构造中间节点，或者通过递归函数的返回值来添加/删除节点。求普通二叉树的属性，使用后序遍历，先求左右子树的属性，再根据左右子树的属性来求当前节点的属性。对于二叉搜索树的属性，使用中序遍历，得到一个有序的序列，直接判断是否满足二叉搜索树的性质。

递归三部曲：确定递归函数的参数和返回值，确定终止条件，确定单层递归的逻辑。

第9章回溯算法

回溯三部曲：确定回溯函数的返回值和参数，确定回溯函数的终止条件，确定回溯搜索的遍历过程

void backtrack(参数列表) {
    if (终止条件) {
        // 处理结果
        return;
    }
    for (选择 : 选择列表) {
        // 做选择
        backtrack(参数列表);
        // 撤销选择
    }
}

例题：组合总和（可重复）思路：排序+简易剪枝如果有重复元素，但每一个元素只能用一次，则需要考虑跳过重复元素，在记录visited数组时，只有当当前元素与前一个元素相同且前一个元素未被访问过时，才跳过当前元素。

void backtrack(vector<int>& candidates, int target, vector<int>& path, vector<vector<int>>& result, int start) {
    if (target == 0) {
        result.push_back(path);
        return;
    }
    for (int i = start; i < candidates.size(); ++i) {
        if (candidates[i] > target) break; // 简易剪枝
        path.push_back(candidates[i]);
        backtrack(candidates, target - candidates[i], path, result, i); // 可重复使用当前元素，传入i
        path.pop_back();
    }
}

例题：全排列针对全排列的去重有两种方式，一种是树层剪枝，另一种是树枝剪枝。树层剪枝：在同一层中，如果当前元素与前一个元素相同且前一个元素未被访问过，则跳过当前元素。树枝剪枝：在递归过程中，如果当前元素与前一个元素相同且前一个元素已经被访问过，则跳过当前元素。这保证了在同一树枝上不会重复使用相同的元素，从而避免生成重复的排列。等同于一种反向去重方式。

第10章贪心算法

使用局部最优推断全局最优的算法设计方法。要证明一半需要使用反证法或者数学归纳法，但一般不做要求。

例题：买卖股票的最佳时机观察到多天的收益可以分解为每天的收益之和，因此只需要累加每天的正收益即可。

int maxProfit(vector<int>& prices) {
    int maxProfit = 0;
    for (size_t i = 1; i < prices.size(); ++i) {
        if (prices[i] > prices[i - 1]) {
            maxProfit += prices[i] - prices[i - 1];
        }
    }
    return maxProfit;
}

例题：跳楼梯每个台阶都有一个对应的跳跃能力，表示从该台阶可以跳跃的最大距离。我们需要用最少的跳跃次数从第一个台阶跳到最后一个台阶。注意：只要有一个台阶能够跳到终点，就不需要考虑后续的台阶了。有个细节上的小优化，我们只需遍历到终点的前一个台阶，若之前的台阶的终点超过了这个台阶，步数就不需要增加了；反之，步数一定要增加1。

int jump(vector<int>& nums) {
    int jumps = 0;
    int currentEnd = 0; // 当前跳跃的终点
    int farthest = 0; // 当前跳跃能够到达的最远位置
    for (size_t i = 0; i < nums.size() - 1; ++i) {
        farthest = max(farthest, i + nums[i]);
        if (i == currentEnd) { // 到达当前跳跃的终点
            jumps++;
            currentEnd = farthest; // 更新当前跳跃的终点
        }
    }
    return jumps;
}

例题：合并区间首先对区间按照起始位置进行排序，然后遍历排序后的区间列表，如果当前区间的起始位置小于等于上一个合并区间的结束位置，说明两个区间有重叠，可以合并；否则，说明当前区间与上一个合并区间没有重叠，可以将上一个合并区间加入结果列表，并更新当前合并区间为当前区间。最后别忘了将最后一个合并区间加入结果列表。

第11章动态规划

动态规划问题可以分为五部曲：

定义状态：确定dp数组的含义，dp[i]表示什么。
确定状态转移方程：根据问题的要求，找到dp[i]与之前状态之间的关系。
确定初始状态：根据状态转移方程，确定dp数组的初始值。
确定计算顺序：根据状态转移方程，确定dp数组的计算顺序，通常是从小到大或者从大到小。
举例推导dp数组：通过具体的例子，推导dp数组的值，验证状态转移方程的正确性。

例题：整数拆分因为整数拆分问题需要至少拆分成两个正整数，所以我们需要考虑dp数组的定义，dp[i]表示将整数i拆分成至少两个正整数的最大乘积。所以我们需要将dp数组同两个表达式进行比较，分别为dp[i]和j * (i - j)，以及j * dp[i - j]，其中j表示拆分的第一个整数，i - j表示剩余的整数。我们需要在这两者中取最大值，来更新dp[i]的值。

例题：零钱兑换是一个完全背包问题，但要注意先遍历物品，再遍历背包容量，这样才能保证每个物品可以被重复使用。否则会出现1+5和5+1两种情况，导致结果重复。

例题：单词拆分我们可以使用一个布尔类型的dp数组，dp[i]表示字符串s的前i个字符是否可以被空格拆分成一个或多个在字典中出现的单词。初始状态dp[0]为true，表示空字符串可以被拆分。对于每个位置i，我们需要检查之前的位置j，如果dp[j]为true，并且s[j:i]在字典中出现过，那么我们就可以将dp[i]更新为true。

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 (size_t i = 1; i <= s.size(); ++i) {
        for (size_t j = 0; j < i; ++j) {
            // substr(j, i - j)表示从位置j开始，长度为i-j的子字符串，即s[j:i]，也可以用find函数来判断s[j:i]是否在字典中出现过 - wordSet.find(s.substr(j, i - j)) != wordSet.end()
            if (dp[j] && wordSet.count(s.substr(j, i - j))) {
                dp[i] = true;
                break; // 找到一个有效的拆分，跳出内层循环
            }
        }
    }
    return dp[s.size()];
}

例题：不相交的线段给定两个长度相同的数组A和B，数组中的元素分别表示在数轴上的点。我们需要连接A中的点和B中的点，要求连接的线段不相交，求最多可以连接多少条线段。思路：我们可以将问题转化为求最长公共子序列（LCS）的问题。

例题：两个字符串的删除操作给定两个字符串word1和word2，我们需要通过删除字符的方式使得两个字符串相等，求最少需要删除多少个字符。思路：我们可以将问题转化为求最长公共子序列（LCS）的问题。最长公共子序列的长度表示两个字符串中最长的公共子序列的长度，那么我们需要删除的字符数就是两个字符串的长度之和减去最长公共子序列的长度的两倍。如果从朴素的dp数组出发，我们可以定义dp[i][j]表示word1的前i个字符和word2的前j个字符的使得能够使字符串相同的最少删除操作数。状态转移方程如下：若word1[i-1] == word2[j-1]，则dp[i][j] = dp[i-1][j-1]，表示当前字符相同，不需要删除。若word1[i-1] != word2[j-1]，则dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1，表示需要删除一个字符，选择删除word1的字符还是删除word2的字符。

例题：编辑距离编辑距离是指将一个字符串转换成另一个字符串所需要的最少操作数，可以使用删除，增加或替换字符的办法，需要注意增加字符可以看作另一个字符串删除字符的反向操作，因此状态转移方程如下：若word1[i-1] == word2[j-1]，则dp[i][j] = dp[i-1][j-1]，表示当前字符相同，不需要操作。若word1[i-1] != word2[j-1]，则dp[i][j] = min({dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 1})，表示需要进行操作，选择删除word1的字符，增加word2的字符，还是替换字符。

例题：回文子串数我们可以开一个bool数组dp[i][j]，表示字符串s的子串s[i:j]是否是回文串。初始状态是所有长度为1的子串都是回文串，即dp[i][i] = true。对于长度大于1的子串，如果s[i] == s[j]，并且dp[i+1][j-1]为true，那么dp[i][j]也为true。我们需要遍历所有的子串，统计dp数组中为true的个数，即为回文子串的数量。注意遍历顺序需要从短到长，这样才能保证在计算dp[i][j]时，dp[i+1][j-1]已经被计算过了。同样，我们还可以使用双指针法来解决这个问题。对于每个中心点，我们可以向两边扩展，统计回文子串的数量。中心点可以是一个字符，也可以是两个字符之间的位置，这样可以覆盖所有长度为奇数和偶数的回文子串。

关于图论之前的内容就到此结束啦，后续的内容会继续讲解图论相关的算法和数据结构。

跟着karl学算法

第4章 链表

第5章 哈希表

第6章 字符串

第7章 栈与队列

第8章 二叉树

第9章 回溯算法

第10章 贪心算法

第11章 动态规划