重生之我要当分子

分类

题解(3)

/ 注册

全部文章（共295篇）

题解 | 分割等和子集

解题思路这是一个01背包问题的变体：问题分析：目标：找到一些数，使其和等于剩余数之和等价于：找到一些数，使其和等于总和的一半因为：如果一部分和为，那么剩余部分也为解题步骤：先求出数组总和如果是奇数，直接返回 false 问题转化为：能否从数组中选择一些数，使其...

2024-12-23

0 14

题解 | 兑换零钱

解题思路问题分析：每种面值的货币可以使用任意张（完全背包特征）目标是找到组成的最少货币数无法组成时返回 -1 动态规划设计：状态定义：表示组成金额所需的最少货币数初始化：，其他为无穷大状态转移：其中是当前面值优化：使用一维数组（滚动数组） ...

2024-12-23

0 13

题解 | 最少的完全平方数

解题思路这是一个完全背包问题的变体：问题分析：目标：找到最少个数的完全平方数，使其和为每个完全平方数可以重复使用需要找到所有小于等于的完全平方数动态规划设计：状态定义：表示和为的最少完全平方数个数初始化：，其他为无穷大状态转移：其中是小于等于的完...

2024-12-23

0 18

题解 | 【模板】完全背包

解题思路这是一个完全背包问题的变体，需要解决两个子问题：问题分析：第一问：求背包能装下的最大价值（不要求装满）第二问：求背包恰好装满时的最大价值（要求装满）每种物品可以使用无限次状态定义：：容量为j时能装下的最大价值（不要求装满）：容量为j时恰好装满的最大价值（要求装满...

2024-12-23

0 17

题解 | 【模板】01背包

解题思路问题分析：第一问：求背包能装下的最大价值（不要求装满）第二问：求背包恰好装满时的最大价值（要求装满）状态定义：：容量为时能装下的最大价值（不要求装满）：容量为时恰好装满的最大价值（要求装满）初始化：全部初始化为（表示空背包，价值为）除了...

2024-12-23

0 18

题解 | [NOIP2001]装箱问题

解题思路这是一个背包问题：状态定义：表示是否可以装到体积最终答案是V减去最大可装体积状态转移：其中是第个物品的体积边界条件：其他初始化为最终结果：找到最大的可装体积返回代码 c++ java pyth...

2024-12-23

0 17

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

解题思路这是一个动态规划问题，需要考虑马的控制点：首先计算出马的所有控制点：马的位置所有满足且的点定义表示从到的路径数状态转移方程：如果不是马的控制点：如果是马的控制点：边界条件：（如果起点不是马的控制点）代码 c++ ja...

2024-12-23

0 19

题解 | 正则表达式匹配

解题思路这是一个动态规划问题，需要考虑多种匹配情况：定义表示的前个字符和的前个字符是否匹配对于的不同情况：如果是普通字符：需要如果是'.'：可以匹配任意字符如果是'*'：可以匹配0次或多次前面的字符对于'*'的情况需要考虑：匹配次：匹配多次：...

2024-12-23

0 36

题解 | 有多少个不同的二叉搜索树

解题思路定义表示个节点能构成的不同二叉搜索树的数量对于每个节点数：可以选择到中的任何一个数作为根节点左子树由小于根节点的数构成右子树由大于根节点的数构成状态转移方程：，从到其中是左子树节点数，是右子树节点数边界条件：代码 c+...

2024-12-23

0 16

题解 | 乘积为正数的最长连续子数组

解题思路这是一个动态规划问题，需要同时维护正积和负积的长度：使用两个变量：：以当前位置结尾的最长正积子数组长度：以当前位置结尾的最长负积子数组长度对于每个新的数字，根据其正负性：如果：加，如果存在则加如果：新（如果存在），新如果：重置和为 ...

2024-12-23

0 24