CroMarmot

分类

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

/ 注册

全部文章（共154篇）

题解 | #丢棋子问题#

丢棋子问题（动态规划）题意 n+1层楼,k个棋子,每次扔一个,如果坏了不能重复使用,没有坏可以重复使用,找到最高德不会摔坏层数问最坏情况需要几次思路分析 1个棋子的情况只有一个棋子,摔坏了就没得猜了,只能从低到高反复用 f(i,1) = i; 2个棋子的情况假设选取从j层丢第一个棋子 ...

C++ 动态规划

2022-02-04

0 484

题解 | #子数组的最大累加和问题#

子数组的最大累加和问题（贪心）题意给一个数字数组，求子数组和的最大值思路分析对于长度大于1的任意答案，考虑能否从这个答案眼花出更优的答案如果答案选择数组两端有负数那么把负数去掉，会得到更大的答案，所以两端一定都不是负数如果答案两端外还有正数那么包含这些正数，会得到更大的答案，所以...

C++ 贪心

2022-02-04

0 410

题解 | #买卖股票的最好时机(三)#

买卖股票的最好时机(三)（动态规划）题意数值数组,最多两次买卖,两次买卖不重叠,问最大收益思路分析状态设计主要有数组遍历下标和买卖状态所以不妨设状态为[下标][买的次数][卖的次数]=当前最大收益递推关系注意到两次买卖不重叠,所以卖的次数+1>=买的次数>=卖的次数, 同...

C++ 动态规划

2022-02-04

0 399

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

把数字翻译成字符串（动态规划）题意给定一个数字串,它是由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

动态规划用法总结（二）

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

动态规划题解

2022-02-02

0 478

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

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

C++ 动态规划

2022-02-02

12 568