静寂旮旯

题解

/ 注册

全部文章 / 题解（共43篇）

题解 | #计算字符串的编辑距离#

解题思路：知道用dp，那么dp[i][j]表示在动态规划过程中表示字符串s1走到i位置，以及字符串s2走到j位置，所需要的最短字符串距离（需要修改的最小次数）一般情况下，dp[i][j]应该是通过三种操作（插入一个字符，删除一个字符，以及修改一个字符）得到的最小操作次数，先要判断一下s1[i]...

C++ 动态规划

2022-04-26

0 206

题解 | #最长公共子序列(一)#

解题思路：利用dp[i][j]表示以s1以i为结尾的子串，s2以j为结尾的子串中有最长的公共子序列的长度，那么普遍情况i != 0 and j != 0i\ !=\ 0\ and\ j\ !=\ 0i != 0&nb...

C++ 动态规划

2022-04-26

0 277

题解 | #滑雪#

解题思路：关键点，是找到起始的位置，在输入地图的同时，把点(i,j)的高度和其坐标保存下来pointshight(i,j)points_{hight(i,j)}pointshight(i,j),再将points按照hight排序。那么拍完序以后的内容就是我们要处理点的顺序。接下来只要对于po...

C++ 动态规划

2022-04-24

1 355

题解 | #信封嵌套#

解题思路：对等于求解最长上升子序列，先将输入按照升序排列。然后求解。对于当前信封i有：在此之前多所有嵌套0<=j<i0<=j<i0<=j<i只要满足v[i].first > v[j].first && v[i].second >...

C++ 动态规划

2022-04-24

0 368

题解 | #龙与地下城游戏问题#

解题思路：入坑思路：起点和终点搞反，即把坐标（n-1，m-1）作为最终解出口。发现问题在求解的过程中总是要回溯到从（0，0）点到当前位置所经过路径上的血瓶计算，感觉问题始终在搞清和没搞清之间，非常痛苦。正确思路：是从（n-1，m-1）点到（0，0）点的求解，在一路走的过程当中只需要考虑当前存...

C++ 动态规划

2022-04-24

3 452

题解 | #合唱队形#

解题思路：队形的特征是从T1<...<Ti>...>TkT_1 <...< T_i >...>T_kT1<...<Ti>...>Tk,(1<=i<=k)(1 <= i <= k)(1<=i...

C++ 动态规划

2022-04-15

0 244

题解 | #拦截导弹#

解题思路：入坑思路，求得最长不严格下降子序列以后，思路一直在记录经历过的点上，思索良久发现不可行。最后查看dp数组中的值，想发现一些规律，迷惑地发现，只要在dp数组中求出严格上升子序列的个数就可以获得答案，结果过了5个测试点后挂了。接下来没有任何思路了。通过看题解知道了一个牛逼的Dilwort...

C++ 动态规划

2022-04-15

0 386

题解 | #最长上升子序列(一)#

解题思路1：首先搞清楚几个问题，到结尾点的最长上升子串应该思考成为，不是以结尾下表i结尾的子串。但是需要知道以i结尾的子串的长度。最终只要取出其中以某个点为结尾的最大长度子串就是要求的答案。递归的思维方式来解决此题，求以最后结尾点i为结束的子串长度dp[i]dp[i]dp[i]只要比较节点0～...

C++ 动态规划

2022-04-14

0 338

题解 | #[NOIP2002 普及组] 过河卒#

解题思路：利用二维数组dp 卒子只能两个方向走，一个是向右，一个是向下。可得状态方程dp[i][j]=dp[i−1][j]+dp[i][j−1]dp[i][j] = dp[i-1][j] + dp[i][j-1]dp[i][j]=dp[i−1][j]+dp[i][j−1]。在处理马点的时候，应...

C++ 动态规划

2022-04-13

7 438

题解 | #矩阵的最小路径和#

解题思路：到达出口只能从出口左边或者上边来，这样就很容易写出递归式,并且进行记忆化搜索。也可以使用状态方程dp[i][j]=min(dp[i−1][j],dp[i][j−1])+v[i][j]dp[i][j] = min(dp[i-1][j], dp[i][j-1])+v[i][j]dp[i][...

C++ 动态规划

2022-04-11

2 347