解题思路 这是一个动态规划问题，需要考虑多种匹配情况：  定义  表示  的前  个字符和  的前  个字符是否匹配 对于  的不同情况：  如果是普通字符：需要  如果是'.'：可以匹配任意字符 如果是'*'：可以匹配0次或多次前面的字符   对于'*'的情况需要考虑：  匹配  次： 匹配多次：    代码   c++   java   python   #include <iostream> #include <string> #include <vector> using namespace std; bool isMatch(string str,...

解题思路  定义  表示  个节点能构成的不同二叉搜索树的数量 对于每个节点数 ：  可以选择  到  中的任何一个数作为根节点 左子树由小于根节点的数构成 右子树由大于根节点的数构成   状态转移方程：  ， 从  到  其中  是左子树节点数， 是右子树节点数   边界条件：  代码   c++   java   python   #include <iostream> #include <vector> using namespace std; int numTrees(int n) { vector<long long> dp(n + 1, 0); ...

解题思路 这是一个动态规划问题，需要同时维护正积和负积的长度：  使用两个变量：  ：以当前位置结尾的最长正积子数组长度 ：以当前位置结尾的最长负积子数组长度   对于每个新的数字 ，根据其正负性：  如果 ： 加 ， 如果存在则加  如果 ：新 （如果  存在），新  如果 ：重置  和  为    维护全局最大长度   代码   c++   java   python   #include <iostream> #include <vector> using namespace std; int getMaxLen(vector<int>& nu...

解题思路 这是一个二维的最长递增子序列()问题，可以通过以下步骤解决：  首先对信封按照宽度升序排序，当宽度相同时按照长度降序排序 这样排序后，我们只需要在长度上找最长递增子序列 使用二分查找优化的  算法：  维护一个数组 ， 表示长度为  的递增子序列的最小结尾值 对于每个数，二分查找它在  中的位置并更新 这样可以达到  的时间复杂度。    代码   c++   java   python   #include <iostream> #include <vector> #include <algorithm> using namespace std;...

解题思路 这是最大子数组和的变种，需要考虑环形的情况。可以通过以下思路解决：  环形数组的最大子数组和有两种可能：  不跨越边界的普通最大子数组和（使用  算法） 跨越边界的最大子数组和（等于总和减去最小子数组和）   对于跨越边界的情况：  总和减去中间的最小子数组和 相当于首尾相连的部分   特殊情况：  如果所有元素都是负数，返回最大的那个负数 如果最小子数组和等于总和，说明所有数都是负数    代码   c++   java   python   #include <iostream> #include <vector> #include <algorit...

解题思路 这是一个动态规划问题，但需要同时维护最大值和最小值，因为：  当遇到负数时，最小值乘以负数可能变成最大值 当遇到正数时，最大值乘以正数仍然是最大值 当遇到0时，需要重新开始计算  具体步骤：  维护两个  数组： 和   表示以  结尾的子数组的最大乘积  表示以  结尾的子数组的最小乘积 遇到新的数时，需要考虑三种情况：  当前数自己 当前数乘以之前的最大值 当前数乘以之前的最小值    代码   c++   java   python   #include <iostream> #include <vector> #include <algorith...

解题思路 这是打家劫舍问题的变种，房屋首尾相连形成环形。可以通过以下步骤解决：  由于首尾相连，我们可以将问题拆分为两种情况：  偷第一家，不能偷最后一家（考虑  的房屋） 不偷第一家，可以偷最后一家（考虑  的房屋）   对于每种情况，使用动态规划求解：   表示到第  个房屋时能偷到的最大金额    最后取两种情况的最大值  代码   c++   java   python   #include <iostream> #include <vector> using namespace std; int rob(vector<int>& nums,...

解题思路 这是一个动态规划问题，可以通过以下步骤解决：  首先统计每个数字出现的次数 对于每个数字 ，如果我们选择了它：  会得到  的分数 会删除所有的  和  不能选择  和    因此可以用  数组记录到当前数字为止能获得的最大分数  表示考虑到数字  时能获得的最大分数  代码   c++   java   python   #include <iostream> #include <vector> #include <unordered_map> using namespace std; long long maxPoints(vector<...

解题思路 这是一个动态规划问题，但需要从终点往起点推导：  创建一个  数组， 表示到达位置  时需要的最小血量 从右下角开始，逆向推导到左上角 对于每个位置 ：  如果是终点，则  否则，   最终  就是所需的最小初始血量  代码   c++   java   python   #include <iostream> #include <vector> #include <algorithm> using namespace std; int minInitialHealth(vector<vector<int>>& ma...

解题思路 编辑距离是一个经典的动态规划问题，我们可以通过以下步骤解决：  创建一个  的二维数组 ，其中  和  分别是两个字符串的长度  表示字符串1的前  个字符转换到字符串2的前  个字符所需的最小操作数 对于每个位置 ，我们有三种可能的操作：  替换： 删除： 插入：    代码   c++   java   python   #include <iostream> #include <string> #include <vector> using namespace std; int minDistance(string word1, string...

解题思路 这是一个二维最大子数组和的问题，可以通过以下步骤解决：  对于每一对可能的行（），我们计算这些行之间每一列的元素和 将二维问题转化为一维问题：把  到  行的每一列的和看作一个一维数组 对这个一维数组求最大子数组和（使用  算法） 遍历所有可能的行对，找到最大的和  代码   c++   java   python   #include <iostream> #include <vector> #include <climits> using namespace std; int kadane(vector<int>& arr)...

解题思路 这是股票买卖的通用版本，需要处理k次交易。我们可以使用动态规划来解决：  创建二维dp数组：  表示第天进行次交易的最大收益 其中范围是，范围是   对于每一天和交易次数，我们有两种选择：  不进行交易：沿用前一天的收益 进行交易：在之前某一天买入，第i天卖出   优化空间复杂度：  使用一维数组记录当前的最大收益 用一个变量记录之前的最大可能收益减去买入价格    代码   c++   java   python   #include <iostream> #include <vector> using namespace std; int maxProfi...

解题思路 这道题是股票买卖的进阶版本，最多允许两次交易。我们可以使用动态规划来解决：  对于每一天，我们有以下几种状态：  第一次买入（） 第一次卖出（） 第二次买入（） 第二次卖出（）   对于每个状态，我们都记录到当前天为止的最大收益 状态转移方程：         代码   c++   java   python   #include <iostream> #include <vector> #include <climits> using namespace std; int maxProfit(vector<int>& pric...

解题思路 这是一道可以多次买卖股票的问题，关键是要理解：  可以在同一天卖出后再买入 只要后一天价格比前一天高，就可以获得这个差价的利润 最终的最大利润就是所有上涨天数的差价之和  因此我们可以：  遍历价格数组 如果当天价格比前一天高，就把差价加到总利润中 这样就能获得最大收益  代码   c++   java   python   #include <iostream> #include <vector> using namespace std; int maxProfit(vector<int>& prices) { int totalProf...