【二叉树】【动态规划】1、斐波那契数+2、零钱兑换
1、遍历：在遍历的过程中就能够解决问题，只需要递归函数的参数即可。 2、子树：只有在遍历完成之后才能解决问题，还需要递归函数的返回值。（需要在后序位置写代码） 动态规划：子树 核心思想是穷举求最值 动态规划三要素： 正确的状态转移方程具有最优子结构存在重叠子问题（暴力穷举效率很低，需要使用备忘录（dp table)来优化穷举过程） 明确状态，明确选择，定义dp数组 回溯算法：树枝 DFS算法：节点 ...
【状态机动态规划 状态压缩】1434. 每个人戴不同帽子的方案数
本文涉及知识点 位运算、状态压缩、枚举子集汇总 动态规划汇总 LeetCode 1434. 每个人戴不同帽子的方案数 总共有 n 个人和 40 种不同的帽子，帽子编号从 1 到 40 。 给你一个整数列表的列表 hats ，其中 hats[i] 是第 i 个人所有喜欢帽子的列表。 请你给每个人安排一顶他喜欢的帽子，确保每个人戴的帽子跟别人都不一样，并返回方案数。 由于答案可能很大，请返回它对 10^9 ...
破解打家劫舍：动态规划与二分查找的高效算法
目录 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...