CroMarmot

分类

未归档(12) 题解(138) 题解总结(4)

/ 注册

全部文章（共34篇）

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

矩阵的最小路径和（动态规划）题意给定一个二维数字数组,求从左上角,走到右下角,路径上值的最小和思路分析相邻关系如果走到最后路径和最小,那么它上一步来源是上方或者左方 int f(i,j){ return min(f(i-1,j),f(i,j-1)) + matrix[i][j]; ...

C++ 动态规划

2022-02-02

0 520

题解 | #编辑距离(二)#

编辑距离(二)（动态规划）题意给定两个字符串,把字符串str1编辑为str2的最小代价,其中插入(ic),删除(dc)和替换(rc)代价分别为给定常数思路分析顺序性无关证明设对str1有一系列操作, 对于一个被增加的字符,一定不会被删除和被修改对于一个被删除的字符,一定不会被增加和被修改...

C++ 动态规划

2022-02-02

0 497

题解 | #最长公共子串#

最长公共子子串（动态规划）题意给定两个字符串,求它们的最长公共子串思路分析公共子串要找s1和s2的公共子串,如果有字符相等s1[i] == s2[j],那么s1[0..i-1]和s2[0..j-1]的后缀公共子串加上相等的字符,就能得到一个更长的公共子串, 所以有, 令s[i][j]表示分...

C++ 动态规划

2022-02-02

1 278

动态规划用法总结（二）

动态规划用法总结（二）动态规划是一个相对高级的工具，有些本身是动态规划的题可以用动态规划以外，当你无法一眼看穿最优解法时，你可以考虑直接使用动态规划。动态规划最常见的解法思路步骤是设计状态设计转移方程对转移方程时间空间优化大多数可以改写为递推边界处理实现优点是，基于状态和状态转...

动态规划题解

2022-02-02

0 460

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

最长公共子序列(二)（动态规划）题意给定两个字符串,求它们的最长公共序列思路分析公共序列要找s1和s2的公共序列,如果有字符相等s1[i] == s2[j],那么s1[0..i-1]和s2[0..j-1]的公共序列加上相等的字符,就能得到一个更长的公共序列, 所以有, 令s[i][j]表示...

C++ 动态规划

2022-02-02

12 568

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

最长上升子序列(三)（动态规划）题意给定一个正整数数组，求它的最长上升子序列，如果有多个，求数值字典序最小的思路分析上升子序列先不考虑最长，先考虑如何找到一个上升子序列每次对于一个值，去找它前面比它小的值就能构成最后把链输出就能得到上升子序列 for(int i = 0;i<ar...

C++ 动态规划

2022-01-31

1 428

题解 | #兑换零钱(一)#

兑换零钱（一）（动态规划）题意给定一个正整数数组，和一个目标值，问最少选取多少个数组中的值能使得其和等于目标值。其中每个值可以被选任意次思路分析最优关系的数学推导假设对于值aim有一个最优方案，这个最优方案中有选一次x,那么上述最优方案中去掉x的剩余的数，是aim-x的一个最优方案。 ...

C++ 动态规划

2022-01-30

0 360

动态规划用法总结（一）

动态规划用法总结（一）动态规划是一个相对高级的工具，有些本身是动态规划的题可以用动态规划以外，当你无法一眼看穿最优解法时，你可以考虑直接使用动态规划。动态规划最常见的解法思路步骤是设计状态设计转移方程对转移方程时间空间优化大多数可以改写为递推边界处理实现优点是，基于状态和状态转...

动态规划题解

2022-01-29

0 554

题解 | #通配符匹配#

通配符匹配（动态规划）题意给一个字符串，和一个通配符表达式，问该字符串是否满足通配符表达式。其中，通配符表达式除了字符外，只支持两种通配符 ?匹配一个任意字符 *匹配任意个任意字符思路分析字符串相等比较如果直接比较两个字符串相等，是按位比较 for(int i = 0;i < le...

C++ 动态规划字符串

2022-01-28

0 498

题解 | #求路径#

求路径（动态规划）题意一个m⋅nm\cdot nm⋅n的地图,从左上角，只能向右或向下，走到右下角，有多少种方案。思路分析什么叫不同的方案呢? 如果把走动的方向，变成序列，两个序列不同，则是不同的方案。如图中红色的走动变成序列是(向右,向右,向右,向右,向下,向下,向下) 蓝色的走动序...

C++ 动态规划数学组合数

2022-01-28

0 328