这几题都挺类似，都是求最长公共子序列，有些题目稍微变了下1143.最长公共子序列体会一下本题和718.最长重复子数组的区别视频讲解：https://www.bilibili.com/video/BV1ye4y1L7CQhttps://programmercarl.com/1143.最长公共子序列.html/***@param{string}text1*@param{

A-AHealthyBreakfast(abc360A)题目大意给定一个字符串包含RMS，问R是否在S的左边。解题思路比较R和S的下标，谁小即谁在左边。神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;intmain(void){ios::sync_with_stdio(false);

 早期文献1：SATO:AnEfficientPropositionalProver HantaoZhang:SATO: An Efficient Propositional Prover. CADE 1997: 272-275@inproceedings{DBLP:conf/cade/Zhang97,author={HantaoZhang},editor={WilliamMcCune},title

引入——最大权独立集问题：最大权独立集：对于一棵树，求出一个点集，这个点集里面的任意两个点都不相连。那么在所有这样的点集中，点权和最大的那个点集，就被成为最大权独立集。想要求出最大权独立集的点权和，我们只需要使用树上dp的方法即可实现设数组f[N][2]其中f[x][0]表示不选择

给你一个下标从 1 开始、大小为 mxn 的整数矩阵 mat，你可以选择任一单元格作为 起始单元格 。从起始单元格出发，你可以移动到 同一行或同一列 中的任何其他单元格，但前提是目标单元格的值 严格大于 当前单元格的值。你可以多次重复这一过程，从一个单元格移动到另一

300.最长递增子序列今天开始正式子序列系列，本题是比较简单的，感受感受一下子序列题目的思路。视频讲解：https://www.bilibili.com/video/BV1ng411J7xPhttps://programmercarl.com/0300.最长上升子序列.html/***@param{number[]}nums*@return{number}*/varlengthOfL

Problem:2741.特别的排列

思路Part1这种题目应该能一眼看出是DP。我们令\(dp_{i,j}\)表示走到\(j\)这个位置，最后一步花了\(i\)的倍数。那么，我们的方程就很好想了：\(dp_{i,j}=\sum_{k=1}^{j-k\timesi\geq0}dp_{i-1,j-k\timesi}\)。因为，我们走到\(j\)的位置只能走\(i\)的倍

思路本题为P3146变式，也算是一道很经典的区间DP题了。因为\(n\leq500\)，考虑区间DP。定义\(dp_{i,j}\)表示操作\([i,j]\)区间剩余长度的最小值。那么，我们可以枚举一个中间值\(k\)，可以显然地得到一个状态转移方程（即不能合二为一的情况）：\[dp_{i,j}=\min(dp_{i,

思路这是一道简单的DP题，DP题的核心就是状态转移。先来说一说\(dp\)数组的含义。\(dp_{i,j}\)表示从\(i\)这个点用\(2^j\)条线段能走到的最远的点。我们再来考虑一下边界情况。因为我们只用\(2^0\)条线段，那么：\(dp_{i,0}=\max(dp_{i,0},r)\)接着，我们递推一

股票问题是一个动态规划的系列问题，前两题并不难，第三题有难度。买卖股票的最佳时机视频讲解：https://www.bilibili.com/video/BV1Xe4y1u77qhttps://programmercarl.com/0121.买卖股票的最佳时机.html/***@param{number[]}prices*@return{number}*/varmaxProfit=

今天就是打家劫舍的一天，这个系列不算难，大家可以一口气拿下。198.打家劫舍视频讲解：https://www.bilibili.com/video/BV1Te411N7SXhttps://programmercarl.com/0198.打家劫舍.html/***@param{number[]}nums*@return{number}*/varrob=function(nums){const

题意给定一个长度为\(n\)的序列\(\{a_1,a_2,\dots,a_n\}\)。现在要在\(a\)选出非空子序列\(\{b_1,b_2,\dots,b_m\}\)，使得所有的\(i\in[1,m]\)，都有\(b_i\bmodi=0\)。求能够选取\(b\)序列的方案数模\(10^9+7\)的值。思路定义\(dp_{i,j}\)表示在\(\{a_1,a

122.买卖股票的最佳时机II本题解法很巧妙，本题大家可以先自己思考一下然后再看题解，会有惊喜！https://programmercarl.com/0122.买卖股票的最佳时机II.html给定一个数组，它的第i个元素是一支给定股票第i天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成

139.单词拆分https://leetcode.cn/problems/word-break/description/给你一个字符串s和一个字符串列表wordDict作为字典。如果可以利用字典中出现的一个或多个单词拼接出s则返回true。注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。输入：s="leetcode

最短路径问题最短路问题是图论中一种重要的算法，本章将包括：目录最短路径问题一.概念1.概念2.解决方案二.\(Flord\)算法1.算法思想2.代码详解3.算法应用及局限性二.\(Djikstra\)算法1.算法思想2.代码详解3.算法特征及其局限性三.\(Bellman-ford\)算法1.算法思路2.代码详解3.

基环树就是比平常的树多一条边，有\(n\)条边，也就有一个环在里面。基本思想就是断环，跑树形\(dp\)，或者用拓扑排序判环去跑环形\(dp\)。树的直径今天才了解到的，用两遍\(dfs\)跑。首先第一遍找到离根节点最远的节点\(u_1\)，然后再从\(u_1\)找到离它最远的节点\(u_2\)，那么

思路首先，对于每一只小猫刚好玩完就被饲养员接走的出发时间必定为\(t_i-sd_i\)。那么，我们令\(a_i=t_i-sd_i\)表示第\(i\)只小猫的最早出发时间。因此，对于第\(k\)时刻出发的饲养员能接到的小猫当且仅当满足\(a_i\leqk\)。然后，我们定义\(dp_{i,j}\)表示用\(i\)

思路定义\(dp_{i,j}\)表示区间\([i,j]\)中回文串的数量。那么，不难得出状态转移方程\(dp_{i,j}=dp_{i-1}+f_{i,j}\)。（其中\(f_{i,j}\)表示左端点大于等于\(i\)，右端点为\(j\)的回文串数量）由此，现在问题转变为了如何求\(f_{i,j}\)。如果我们在求出了\(f_{i+1,j}

思路首先考虑较为普通的DP。定义\(dp_{i,j}\)表示在前\(i\)个位置中，最后一个1在\(j\)的最大分数，显然有：\[dp_{i,j}=\left\{\begin{matrix}\max_{k=1}^{i-1}\{dp_{i-1,k}\}+\sum_{l_k\leqj\wedger_k=i}{a_k}&(i=j)\\dp_{i-1,j}+\sum

思路因为题目与二进制有关，考虑往二进制的方向思考。定义\(dp_{i,j}\)表示在所有的\(n\)个数中，当前在决策对于每一个数在二进制表示下的第\(i\)位是\(0\)还是\(1\)，且和为\(j\)的方案数。因为异或需要满足对于所有\(a_i\)表示为二进制后每一位\(1\)的个数均为偶数

思路首先不难发现一个规律，当\(sum\)为奇数时不可能有解。定义\(dp_{i,j,k,0/1}\)表示A在前\(i\)个数中选出和为\(j\)的\(k\)个数，且第\(i\)个不选/选的方案数。那么，我们只需要对于第\(i\)个数的状态分类讨论就能得到状态转移方程：不选\(i\)，\(dp_{i,j,k,0}=

思路首先假设有两个串\(a,b\)，如果\(b\)是\(a\)的子串，且\(a\neqb\)则不需要考虑\(b\)；如果\(a=b\)，则如需要保留一个\(a\)。做完上述操作后，显然最终的答案是由这些串按照一定顺序拼接起来，再删掉重叠部分。例如：abbcc与ccdde拼接为abbccccdde，发现cc是重复的，所以

思路发现自己与庄家的操作是完全独立的，所以考虑分别计算它们。首先考虑自己的情况，定义\(dp_i\)表示掷出骰子的和为\(i\)获胜的概率，并记\(f(i)\)表示\(x=i\)时就不掷的获胜概率。对于每一步我们要么掷骰子（并且掷出的值等概率的在\(1\simD\)中），要么直接结束。两种情

思路毒瘤数位DP题。首先，你可以用一个vector储存每一个数字出现的次数，然后用map记忆化。然后可以得到如下TLE#8的代码。因为map自带一只\(\log\)所以，考虑将map优化掉。但是，现在每一种数字可能会出现很多次，所以要用vector维护出现次数，但这样必定需要用map一