【C++动态规划 图论】3243. 新增道路查询后的最短距离 I|1567
本文涉及知识点 打开打包代码的方法兼述单元测试 C++动态规划 C++图论 LeetCode3243. 新增道路查询后的最短距离 I 给你一个整数 n 和一个二维整数数组 queries。 有 n 个城市，编号从 0 到 n - 1。初始时，每个城市 i 都有一条单向道路通往城市 i + 1（ 0 <= i < n - 1）。 queries[i] = [ui, vi] 表示新建一条从城市 ui 到城市...
【C++动态规划】1594. 矩阵的最大非负积|1807
本文涉及知识点 下载及打开打包代码的方法兼述单元测试 C++动态规划 LeetCode1594. 矩阵的最大非负积 给你一个大小为 m x n 的矩阵 grid 。最初，你位于左上角 (0, 0) ，每一步，你可以在矩阵中 向右 或 向下 移动。 在从左上角 (0, 0) 开始到右下角 (m - 1, n - 1) 结束的所有路径中，找出具有 最大非负积 的路径。路径的积是沿路径访问的单元格中所有整数的...
【C++动态规划】1458. 两个子序列的最大点积|1823
本文涉及知识点 下载及打开打包代码的方法兼述单元测试 C++动态规划 LeetCode1458. 两个子序列的最大点积 LeetCode3290 和此题几乎相同。 给你两个数组 nums1 和 nums2 。 请你返回 nums1 和 nums2 中两个长度相同的 非空 子序列的最大点积。 数组的非空子序列是通过删除原数组中某些元素（可能一个也不删除）后剩余数字组成的序列，但不能改变数字间相对顺序。比方...
动态规划在斐波那契数列中的应用与优化
1. 题目解析🌜2. 讲解算法原理状态表示状态转移方程初始化填表顺序返回值 🌜3. 编写代码 结语 前言 斐波那契数列是数学领域中一个经典的问题，在计算机科学中也有广泛的应用。从简单的递归算法到优化的动态规划方法，斐波那契数列的求解体现了算法设计和性能优化的精髓。本文将以动态规划为核心，系统地探讨如何高效地计算斐波那契数列，分析不同方法的时间与空间复杂度，并展示动态规划的强大之处。希望通过本研究，为算法设...
【C++动态规划】3144. 分割字符频率相等的最少子字符串|1917
本文涉及知识点 C++动态规划 划分型 LeetCode3144. 分割字符频率相等的最少子字符串 给你一个字符串 s ，你需要将它分割成一个或者更多的 平衡 子字符串。比方说，s == “ababcc” 那么 (“abab”, “c”, “c”) ，(“ab”, “abc”, “c”) 和 (“ababcc”) 都是合法分割，但是 (“a”, “bab”, “cc”) ，(“aba”, “bc”, “...
【C++动态规划 子集状态压缩】2002. 两个回文子序列长度的最大乘积|1869
本文涉及知识点 C++动态规划 位运算、状态压缩、枚举子集汇总 LeetCode2002. 两个回文子序列长度的最大乘积 给你一个字符串 s ，请你找到 s 中两个 不相交回文子序列 ，使得它们长度的 乘积最大 。两个子序列在原字符串中如果没有任何相同下标的字符，则它们是 不相交 的。 请你返回两个回文子序列长度可以达到的 最大乘积 。 子序列 指的是从原字符串中删除若干个字符（可以一个也不删除）后，剩...
【C++动态规划】1411. 给 N x 3 网格图涂色的方案数|1844
本文涉及知识点 C++动态规划 LeetCode1411. 给 N x 3 网格图涂色的方案数 提示 你有一个 n x 3 的网格图 grid ，你需要用 红，黄，绿 三种颜色之一给每一个格子上色，且确保相邻格子颜色不同（也就是有相同水平边或者垂直边的格子颜色不同）。 给你网格图的行数 n 。 请你返回给 grid 涂色的方案数。由于答案可能会非常大，请你返回答案对 10^9 + 7 取余的结果。 示例...
代码随想录算法训练营第40天 | 第九章动态规划 part13
文章目录 第九章 动态规划 part13详细布置647. 回文子串最终 `dp` 数组总结双指针 516. 最长回文子序列 动态规划总结篇 第九章 动态规划 part13 今天我们就要结束动态规划章节了，大家激不激动！！！ 详细布置 647. 回文子串 动态规划解决的经典题目，如果没接触过的话，别硬想，直接看题解。 647. 回文子串 看似很难，实际上确实挺难。 我们将使用输入字符串 s = "aba"...
【LeetCode】动态规划—1964. 找出到每个位置为止最长的有效障碍赛跑路线（附完整Python/C++代码）
动态规划—1964. 找出到每个位置为止最长的有效障碍赛跑路线 前言题目描述基本思路1. 问题定义2. 理解问题和递推关系动态规划递推公式：公式推导：伪代码：核心思想： 3. 解决方法动态规划 + 二分查找 4. 进一步优化5. 小总结 Python代码Python代码解释总结： C++代码C++代码解释总结： 总结 前言 最长有效障碍物路线问题 是一个涉及到 最长递增子序列（LIS） 变种的问题。给定...
【状态机动态规划 状态压缩】1434. 每个人戴不同帽子的方案数
本文涉及知识点 位运算、状态压缩、枚举子集汇总 动态规划汇总 LeetCode 1434. 每个人戴不同帽子的方案数 总共有 n 个人和 40 种不同的帽子，帽子编号从 1 到 40 。 给你一个整数列表的列表 hats ，其中 hats[i] 是第 i 个人所有喜欢帽子的列表。 请你给每个人安排一顶他喜欢的帽子，确保每个人戴的帽子跟别人都不一样，并返回方案数。 由于答案可能很大，请返回它对 10^9 ...