CroMarmot

分类

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

/ 注册

全部文章（共34篇）

题解 | #打家劫舍(二)#

打家劫舍(二) 题意给定一个数字数组，它们构成环，不能选相邻的两个数，问选的数的最大的和是多大方法深搜(TLE) 分析我们递归搜索，每次有可选的起始位置。如果选定这个位置，那么下一层递归，则可选位置从当前位置+2开始如果不选这个位置，那么下一层递归，可选位置从当前位置+1开始在递归过程...

C++ 动态规划

2022-02-21

0 334

题解 | #打家劫舍(一)#

打家劫舍(一) 题意给定一个数字数组，不能选相邻的两个数，问选出的数的最大的和是多大方法深搜(TLE) 分析我们递归搜索，每次有可选的起始位置。如果选定这个位置，那么下一层递归，则可选位置从当前位置+2开始如果不选这个位置，那么下一层递归，可选位置从当前位置+1开始在递归过程中记录选择...

C++ 动态规划

2022-02-21

0 306

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

最长公共子序列(一) 题意给定一个两个字符串，求它们的公共子序列的长度方法深搜(TLE) 分析用两个指针分别指向两个字符串当前比对的位置如果相等，则计数+1向后比较，递归继续如果不等，舍去其中一个字符串你的位置，递归继续所有方案中的最大长度，就是要求的值。变成伪代码就是 dfs(位置...

C++ 动态规划

2022-02-21

0 191

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

最长上升子序列(二) 题意给定一个正整数数组，求它的最长上升子序列的长度方法深搜(TLE) 分析选一个位置开始，作为上升序列的起点，从这个位置向后找比它大的数。以此递归，每次记录长度，并记录所有方案中的最大长度，就是要求的值。变成伪代码就是 dfs(当前位置i,当前上升序列长度cnt):...

C++ 动态规划

2022-02-21

0 260

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

最长上升子序列(一) 题意给定一个正整数数组，求它的最长上升子序列的长度方法深搜(TLE) 分析选一个位置开始，作为上升序列的起点，从这个位置向后找比它大的数。以此递归，每次记录长度，并记录所有方案中的最大长度，就是要求的值。变成伪代码就是 dfs(当前位置i,当前上升序列长度cnt):...

C++ 动态规划

2022-02-21

0 235

动态规划用法总结（三）

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

动态规划题解

2022-02-04

0 258

题解 | #丢棋子问题#

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

C++ 动态规划

2022-02-04

0 322

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

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

C++ 动态规划

2022-02-04

0 287

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

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

C++ 动态规划

2022-02-02

8 391

题解 | #最大正方形#

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

C++ 动态规划

2022-02-02

0 277