【算法|动态规划No.9】leetcodeLCR 091. 粉刷房子
点击直接跳转到该题目 1️⃣题目描述 假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。 当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。 例如，costs[0][0] 表示第 0 号房子粉刷...
【算法|动态规划No.10】leetcode LCR 089. 打家劫舍 & LCR 090. 打家劫舍 II
目录 一、LCR 089. 打家劫舍1️⃣题目描述2️⃣题目解析3️⃣解题代码 二、LCR 090. 打家劫舍 II1️⃣题目描述2️⃣题目解析3️⃣解题代码 一、LCR 089. 打家劫舍 点击可直接跳转到该题目 1️⃣题目描述 一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响小偷偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自...
【算法|动态规划No.11】leetcode53. 最大子数组和
目录 1️⃣题目描述2️⃣题目解析3️⃣解题代码解题代码1：解题代码2： 1️⃣题目描述 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 子数组 是数组中的一个连续部分。 示例1： 示例2： 示例3： 注意： 1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4 2️⃣题目解析 状态表示： dp[i]...
【算法|动态规划No.7】leetcode300. 最长递增子序列
1,6,2,2,7] 的子序列。 示例 1： 示例 2： 示例3： 注意： 1 <= nums.length <= 2500-10^4 <= nums[i] <= 10^4 2️⃣题目解析 本题目使用动态规划来解决此问题。 dp[i]表示以第i个元素结尾的最长递增子序列的长度。通过不断更新以每个元素结尾的最长递增子序列的长度，最终得到整个数组的最长递增子序列的长度。 对于每个位置i，都需要遍历位置i之前的...
代码随想录 动态规划 14
1143. 最长公共子序列 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。 两个字符...
【算法|动态规划No.8】leetcode面试题 17.16. 按摩师
点击直接跳转到该题目 目录 1️⃣题目描述2️⃣题目解析3️⃣解题代码 1️⃣题目描述 一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。 示例1： 示例2： 示例3： 2️⃣题目解析 dp[i]表示i位置为当前的最长按摩时间。根据题目要求，由...
【动态规划刷题 17】回文子串&& 最长回文子串
出：3 解释：三个回文子串: “a”, “b”, “c” 示例 2： 输入：s = “aaa” 输出：6 解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa” 解法（动态规划）： 算法思路： 我们可以先「预处理」⼀下，将所有⼦串「是否回⽂」的信息统计在 dp 表⾥⾯，然后直接在表⾥⾯统计 true 的个数即可。 1.状态表示* 为了能表⽰出来所有的⼦串，我们可以创建⼀个 ...
代码随想录 动态规划Ⅶ
70. 爬楼梯 爬楼梯背包解法：每一次爬的阶数是物品，楼层数是背包容量，排列问题故外层遍历背包容量，内层遍历物品 class Solution: def climbStairs(self, n: int) -> int: dp = [0]*(n + 1) dp[0] = 1 m = 2 # 遍历背包 for j in range(n + 1): # 遍历物品 for step in range(1, m ...
【动态规划刷题 18】（hard）回文子串&& （hard）最长回文子串
释：s 没办法被分割成 3 个回文子字符串。 解法： 算法思路： 题⽬要求⼀个字符串被分成「三个⾮空回⽂⼦串」，乍⼀看，要表⽰的状态很多，有些⽆从下⼿。 其实，我们可以把它拆成「两个⼩问题」： i. 动态规划求解字符串中的⼀段⾮空⼦串是否是回⽂串； ii. 枚举三个⼦串除字符串端点外的起⽌点，查询这三段⾮空⼦串是否是回⽂串。 那么这道困难题就免秒变为简单题啦，变成了⼀道枚举题 代码： bool check...
【面试算法——动态规划 19】最长回文子序列&& （hard）让字符串成为回文串的最少插入次数
516. 最长回文子序列 链接: 516. 最长回文子序列 给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。 示例 1： 输入：s = “bbbab” 输出：4 解释：一个可能的最长回文子序列为 “bbbb” 。 示例 2： 输入：s = “cbbd” 输出：2 解释：一个可能的最长回文子序列为...