【状态机动态规划 状态压缩】1434. 每个人戴不同帽子的方案数
本文涉及知识点 位运算、状态压缩、枚举子集汇总 动态规划汇总 LeetCode 1434. 每个人戴不同帽子的方案数 总共有 n 个人和 40 种不同的帽子,帽子编号从 1 到 40 。 给你一个整数列表的列表 hats ,其中 hats[i] 是第 i 个人所有喜欢帽子的列表。 请你给每个人安排一顶他喜欢的帽子,确保每个人戴的帽子跟别人都不一样,并返回方案数。 由于答案可能很大,请返回它对 10^9 ...
【二叉树】【动态规划】1、斐波那契数+2、零钱兑换
1、遍历:在遍历的过程中就能够解决问题,只需要递归函数的参数即可。 2、子树:只有在遍历完成之后才能解决问题,还需要递归函数的返回值。(需要在后序位置写代码) 动态规划:子树 核心思想是穷举求最值 动态规划三要素: 正确的状态转移方程具有最优子结构存在重叠子问题(暴力穷举效率很低,需要使用备忘录(dp table)来优化穷举过程) 明确状态,明确选择,定义dp数组 回溯算法:树枝 DFS算法:节点 ...
破解打家劫舍:动态规划与二分查找的高效算法
目录 198. 打家劫舍 解法一:一维动态规划 解法二:二维动态规划 213. 打家劫舍 II 思路分析 代码实现 337. 打家劫舍 III 思路分析 代码实现 2560. 打家劫舍 IV 思路分析 参考博客 198. 打家劫舍 如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 ,求今晚能够偷窃到的最高金额。 解法一:一维动态规划 class Solution { public int r...
【题解】55. 跳跃游戏(贪心、数组、动态规划)
https://leetcode.cn/problems/jump-game/description/?envType=study-plan-v2&envId=top-interview-150 class Solution {public: bool canJump(vector<int>& nums) { int n = nums.size(); int lastPos = 0; // 最远可以到...
【划分型动态规划 马拉车 中心扩展】2472. 不重叠回文子字符串的最大数目
如果有不明白的,请加文末QQ群。 本文涉及知识点 划分型动态规划 马拉车 中心扩展 LeetCode2472. 不重叠回文子字符串的最大数目 给你一个字符串 s 和一个 正 整数 k 。 从字符串 s 中选出一组满足下述条件且 不重叠 的子字符串: 每个子字符串的长度 至少 为 k 。 每个子字符串是一个 回文串 。 返回最优方案中能选择的子字符串的 最大 数目。 子字符串 是字符串中一个连续的字符序列...
【最长公共前缀 动态规划】2430. 对字母串可执行的最大删除数
如果有不明白的,请加文末QQ群。 本文涉及知识点 最长公共前缀 动态规划 动态规划汇总 LeetCode 2430. 对字母串可执行的最大删除数 给你一个仅由小写英文字母组成的字符串 s 。在一步操作中,你可以: 删除 整个字符串 s ,或者 对于满足 1 <= i <= s.length / 2 的任意 i ,如果 s 中的 前 i 个字母和接下来的 i 个字母 相等 ,删除 前 i 个字母。 例如,...
leetcode-动态规划-01背包
一、二维数组 1、状态转移方程: 不放物品i:由dp[i - 1][j]推出,即背包容量为j,里面不放物品i的最大价值,此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时,物品i无法放进背包中,所以背包内的价值依然和前面相同。)放物品i:由dp[i - 1][j - weight[i]]推出,dp[i - 1][j - weight[i]] 为背包容量为j - w...
【状态机dp 动态规划】100290. 使矩阵满足条件的最少操作次数
本文涉及知识点 动态规划汇总 状态机dp LeetCode100290. 使矩阵满足条件的最少操作次数 给你一个大小为 m x n 的二维矩形 grid 。每次 操作 中,你可以将 任一 格子的值修改为 任意 非负整数。完成所有操作后,你需要确保每个格子 grid[i][j] 的值满足: 如果下面相邻格子存在的话,它们的值相等,也就是 grid[i][j] == grid[i + 1][j](如果存在)...
【C++刷题】优选算法——动态规划第五辑
最长公共子序列 状态表示: 选取第一个字符串[0,i]区间和第二个字符串[0,j]区间作为研究对象 dp[i][j]: 表示s1的[0,i]区间和s2的[0,j]区间内的所有子序列中,最长公共子序列的长度状态转移方程: text1[i] == text2[j]: dp[i][j] = dp[i-1][j-1] + 1; text1[i] != text2[j]: dp[i][j] = max(dp[i...
【动态规划 区间dp 位运算】100259. 划分数组得到最小的值之和
本文涉及知识点 动态规划 区间dp 位运算 LeetCode100259. 划分数组得到最小的值之和 给你两个数组 nums 和 andValues,长度分别为 n 和 m。 数组的 值 等于该数组的 最后一个 元素。 你需要将 nums 划分为 m 个 不相交的连续 子数组,对于第 ith 个子数组 [li, ri],子数组元素的按位AND运算结果等于 andValues[i],换句话说,对所有的 1...