暴力递归到动态规划（一） 斐波那契数列的动态规划机器人走路初级递归初级动态规划动态规划 先后选牌问题初级递归初级动态规划动态规划 我们可以一句话总结下动态规划 动态规划本质是一种以空间换时间的行为 如果你发现有重复调用的过程 在经过一次之后把结果记下来 下次调用的时候直接用 这就是动态规划 斐波那契数列的动态规划 一般来说我们可以使用递归来解决斐波那契数列问题 代码如下 int fib(int n) {...

目录 1️⃣题目描述2️⃣题目解析3️⃣解题代码 1️⃣题目描述 如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。 例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。 给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。 子数组 是数组中的一个连续序列。 示例1： 示例2： 注意： 1 <= ...

10. 正则表达式匹配 链接: 10. 正则表达式匹配 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。 ‘.’ 匹配任意单个字符 ‘*’ 匹配零个或多个前面的那一个元素 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。 示例 1： 输入：s = “aa”, p = “a” 输出：false 解释：“a” 无法匹配 “aa” 整个字符串。 示例...

点击直接跳转到该题目 目录 1️⃣题目描述2️⃣题目解析3️⃣解题代码 1️⃣题目描述 给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。 下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, co...

115. 不同的子序列 给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。 链接：：https://leetcode.cn/problems/distinct-subsequences/ 示例 1： 输入：s = “rabbbit”, t = “rabbit” 输出：3 解释： 如下所示, 有 3 种可以从 s 中得到 “rabbit” 的...

1 个。正方形的总数 = 6 + 1 = 7. 提示： 1 <= arr.length <= 3001 <= arr[0].length <= 3000 <= arr[i][j] <= 1 解法 动态规划/递推（最优） 本题和 221. 最大正方形 非常类似，使用的方法也几乎相同。 我们用 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示以 ( i , j ) (i,j) (i...

点击直接跳转到该题目 目录 1️⃣题目描述2️⃣题目解析3️⃣解题代码 1️⃣题目描述 在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。 现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足以下两点： nums1[i] == nums2[j]且绘制的直线不与任何其他连线（非水平线）相交。 示例 1： 示例2： 示例3： 注意： ...

点击直接跳转到该题目 目录 1️⃣题目描述2️⃣题目解析3️⃣解题代码 1️⃣题目描述 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，"ace" 是 "abcde" 的子序...

点击直接跳转到该题目 目录 1️⃣题目描述2️⃣题目解析3️⃣解题代码 1️⃣题目描述 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。 示例1： 示例2： 注意： 1 <= nums.length <= 2001 <= nums[i] <= 100 2️⃣题目解析 状态表示： dp[i][j]：从前i个数中进行挑选，能够凑成j这个...

583. 两个字符串的删除操作 给定两个单词 word1 和 word2 ，返回使得 word1 和  word2 相同所需的最小步数。 每步 可以删除任意一个字符串中的一个字符。 思路：dp[i][j]数组表示使得 word1[:i] 和  word2[:j] 相同所需的最小步数。当word1[i-1]==word2[j-1]时，dp[i][j] = dp[i-1][j-1], 当word1[i-1] ...