CroMarmot

题解

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

/ 注册

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

题解 | #把数字翻译成字符串#

把数字翻译成字符串（动态规划）题意给定一个数字串,它是由a-z映射成1-26得到的,问它的原文有多少种可能思路分析能被反向的条件因为是a-z映射成1-26得到的所以每个被反向映射的值一定在1-26之间所以判断是1位还是2位,且值满足范围,没有前导0 能被反向的1位数只有1-9可以被反...

C++ 动态规划

2022-02-02

8 541

题解 | #最大正方形#

矩阵的最小路径和（动态规划）题意给定一个二维0/1数组,求由1构成的最大的正方形是多少思路分析题意转换把问题转换,变成给你同样的数组,你可以从任何0值出发,向右,向下,或向右下走,记录每个格子所需要的最少步数求最少步数的最大值证明等价转换后的题意,意味着每个1的格子的值,表示的是它左...

C++ 动态规划

2022-02-02

0 402

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

矩阵的最小路径和（动态规划）题意给定一个二维数字数组,求从左上角,走到右下角,路径上值的最小和思路分析相邻关系如果走到最后路径和最小,那么它上一步来源是上方或者左方 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

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

最长公共子序列(二)（动态规划）题意给定两个字符串,求它们的最长公共序列思路分析公共序列要找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

题解 | #最长回文子串#

最长回文子串（遍历）题意给定字符串中最长回文子串有多长思路分析判断回文串对于是不是回文串，可以通过从字符串的两边开始比较对称位置 for(int i = 0;i < s.length();i++){ if(s[i] != s[s.length()-1-i])return fa...

C++ 数组遍历

2022-01-30

0 370

题解 | #子数组最大乘积#

子数组最大乘积（贪心）题意一个有正负和零的double数组中，最大的子数组乘积为多少思路分析快速运算乘积如果数组中没有零计算数组一段的乘积，相当于计算从数组起始到结束的乘积，除以起始到数组开始之前的积 f(i,j) = premul[j] / premul[i-1] 局部最优对于选...

C++ 贪心

2022-01-29

0 464