新闻详情

新闻详情

首页 / 资讯中心 / 详情

简单多状态dp问题

发布时间:2026/11/19 5:30:19来源:尧图网络
简单多状态dp问题
1.按摩师面试题 17.16. 按摩师 - 力扣LeetCode1.题目解析一个有名的按摩师会收到源源不断的预约请求每个预约都可以选择接或不接。在每次预约服务之间要有休息时间因此她不能接受相邻的预约。给定一个预约请求序列替按摩师找到最优的预约集合总预约时间最长返回总的分钟数。2.算法原理1.状态表示根据经验题目要求f[i]表示:选择到i位置的时候,选择nums[i],此时最长预约时长g[i]表示:选择到i位置的时候,不选择nums[i],此时最长预约时长2.状态转移方程f[i] g[i-1]nums[i]g[i] max{f[i-1],g[i-1])3.初始化f[0]nums[0]g[0]04.填表顺序从左到右,两个表都要填5.返回值max(f[n-1],g[n-1])3.代码实现class Solution { public int massage(int[] nums) { int n nums.length; int[] f new int[n]; int[] g new int[n]; if(n0){ return 0; } f[0] nums[0]; for(int i 1;in;i){ f[i] g[i-1] nums[i]; g[i] Math.max(f[i-1],g[i-1]); } return Math.max(f[n-1],g[n-1]); } }2.打家劫舍213. 打家劫舍 II - 力扣LeetCode1.题目解析你是一个专业的小偷计划偷窃沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都都围成一圈 这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统,如果两间相邻的房子在同一时间被小偷闯入,系统会自动报警给定一个代表每个房屋存放金额的非负整数数组计算你在不触发警报装置的情况下 今晚能够偷窃到的最高金额。2.算法原理这道题和打家劫舍一的不同是首位是相连的3.代码实现class Solution { public int rob(int[] nums) { int n nums.length; return Math.max(myRob(nums,1,n-1),nums[0]myRob(nums,2,n-2)); } public int myRob(int[] nums,int left,int right){ if(leftright){ return 0; } int n nums.length; int[] f new int[n]; int[] g new int[n]; f[left] nums[left]; for(int i left1;iright;i){ f[i] g[i-1] nums[i]; g[i] Math.max(f[i-1],g[i-1]); } return Math.max(f[right],g[right]); } }3.删除并获得点数740. 删除并获得点数 - 力扣LeetCode1.题目解析给你一个整数数组nums你可以对它进行一些操作。每次操作中选择任意一个nums[i]删除它并获得nums[i]的点数。之后你必须删除所有等于nums[i] - 1和nums[i] 1的元素。开始你拥有0个点数。返回你能通过这些操作获得的最大点数2.算法原理arr[i]表示i这个数出现的总和问题就转换成在arr中进行打家劫舍3.代码实现class Solution { public int deleteAndEarn(int[] nums) { int mx0; for(int x:nums){ mxMath.max(x,mx); } int[] arrnew int[mx1]; for(int x:nums){ arr[x]x; } int[] fnew int[mx1]; int[] gnew int[mx1]; f[0]arr[0]; for(int i1;imx;i){ f[i]g[i-1]arr[i]; g[i]Math.max(f[i-1],g[i-1]); } return Math.max(f[mx],g[mx]); } }4.粉刷房子LCR 091. 粉刷房子 - 力扣LeetCode1.题目解析假如有一排房子共n个每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。当然因为市场上不同颜色油漆的价格不同所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个n x 3的正整数矩阵costs来表示的。例如costs[0][0]表示第 0 号房子粉刷成红色的成本花费costs[1][2]表示第 1 号房子粉刷成绿色的花费以此类推。请计算出粉刷完所有房子最少的花费成本。2.算法原理1.状态表示根据经验题目要求dp[i][0]表示刷到i位置最后一个位置刷红色,此时的最小花费dp[i][1]表示刷到i位置最后一个位置刷蓝色,此时的最小花费dp[i][2]表示刷到i位置最后一个位置刷绿色,此时的最小花费2.状态转移方程dp[i][0] min(dp[i-1][1],dp[i-1][2])cost[i][0];dp[i][1] min(dp[i-1][0],dp[i-1][2])cost[i][1];dp[i][2] min(dp[i-1][1],dp[i-1][0]) cost[i][2];3.初始化4.填表顺序从左到右,从上到下5.返回值min(dp[n-1][0],dp[n-1][1],dp[n-1][2])3.代码实现class Solution { public int minCost(int[][] costs) { int n costs.length; int[][] dp new int[n][3]; dp[0][0] costs[0][0]; dp[0][1] costs[0][1]; dp[0][2] costs[0][2]; for(int i 1;in;i){ dp[i][0] Math.min(dp[i-1][1],dp[i-1][2]) costs[i][0]; dp[i][1] Math.min(dp[i-1][0],dp[i-1][2]) costs[i][1]; dp[i][2] Math.min(dp[i-1][1],dp[i-1][0]) costs[i][2]; } return Math.min(Math.min(dp[n-1][0],dp[n-1][1]),dp[n-1][2]); } }5.买卖股票的最佳时机含冷冻期309. 买卖股票的最佳时机含冷冻期 - 力扣LeetCode1.题目解析给定一个整数数组prices其中第prices[i]表示第i天的股票价格 。​设计一个算法计算出最大利润。在满足以下约束条件下你可以尽可能地完成更多的交易多次买卖一支股票:卖出股票后你无法在第二天买入股票 (即冷冻期为 1 天)。注意:你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。2.算法原理1.状态表示根据经验题目要求dp[i][0] 买入dp[i][1] 可交易dp[i][2] 冷冻期2.状态转移方程dp[i][0]max(dp[i-1][0],dp[i-1][1]-price[i])dp[i][1]max(dp[i-1][1],dp[i-1][2])dp[i][2]dp[i-1][0]price[i]3.初始化dp[0][0]-p[0]dp[0][1]0;dp[0][2]0;4.填表顺序从左到右5.返回值返回max(dp[n-1][0],dp[n-1][1],dp[n-1][2])3.代码实现class Solution { public int maxProfit(int[] p) { int n p.length; int[][] dp new int[n][3]; dp[0][0] -p[0]; for(int i 1;in;i){ dp[i][0] Math.max(dp[i-1][0],dp[i-1][1]-p[i]); dp[i][1] Math.max(dp[i-1][1],dp[i-1][2]); dp[i][2] dp[i-1][0] p[i]; } return Math.max(Math.max(dp[n-1][0],dp[n-1][1]),dp[n-1][2]); } }6.买卖股票的最佳时机含手续费714. 买卖股票的最佳时机含手续费 - 力扣LeetCode1.题目解析给定一个整数数组prices其中prices[i]表示第i天的股票价格 整数fee代表了交易股票的手续费用。你可以无限次地完成交易但是你每笔交易都需要付手续费。如果你已经购买了一个股票在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。注意这里的一笔交易指买入持有并卖出股票的整个过程每笔交易你只需要为支付一次手续费。2.算法原理1.状态表示根据经验题目要求dp[i]表示第i天结束之后,能获得的最大利润dp[i][0]表示第i天买入dp[i][1]表示第i天卖出3.代码实现class Solution { public int maxProfit(int[] prices, int fee) { int nprices.length; int[] fnew int[n]; int[] gnew int[n]; f[0]-prices[0]; g[0]0; for(int i1;in;i){ f[i]Math.max(g[i-1]-prices[i],f[i-1]); g[i]Math.max(f[i-1]prices[i]-fee,g[i-1]); } return Math.max(f[n-1],g[n-1]); } }7.买卖股票的最佳时机123. 买卖股票的最佳时机 III - 力扣LeetCode1.题目解析给定一个数组它的第i个元素是一支给定的股票在第i天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。注意:你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。2.算法原理1.状态表示根据经验题目要求f[i][j]表示在第i天结束之后,完成了j次交易,此时出入买入状态的最大利润g[i][j]表示在第i天结束之后,完成了j次交易,此时处于卖出状态的最大利润2.状态转移方程f[i][j]max(f[i-1][j],g[i-1][j]-p[i])g[i][j]max(g[i-1][j],f[i-1][j-1]p[i])3.初始化第0行从第一个位置开始负无穷(更好的做法是最小值选-0x3f3f3f3f,这样不会越界)4.填表顺序从上往下,从左到右5.返回值g表中最后一行的最大值3.代码实现class Solution { public int maxProfit(int[] p) { int np.length; int[][] fnew int[n][3]; int[][] gnew int[n][3]; int min0x3f3f3f3f; for(int i0;i3;i){ f[0][i]-min; g[0][i]-min; } f[0][0]-p[0]; g[0][0]0; for(int i1;in;i){ for(int j0;j3;j){ f[i][j]Math.max(f[i-1][j],g[i-1][j]-p[i]); g[i][j]g[i-1][j]; if(j-10){ g[i][j]Math.max(g[i][j],f[i-1][j-1]p[i]); } } } int ret0; for(int j0;j3;j){ retMath.max(ret,g[n-1][j]); } return ret; } }
网站建设高端定制企业官网
RELATED

相关资讯

更多精彩内容,欢迎继续阅读

较早相关资讯

最新相关资讯

【外设】之大彩串口显示屏 2026/11/18 21:21:17

【外设】之大彩串口显示屏

大彩串口屏初步使用 1 .官网下载 STM32 屏幕 GUI 设计资料 http://www.gz-dc.com/category/typeid/4112 找到 STM32 Keil 工程,移植相关代码因项目而异进行移植,由于项目简单,本人只对用到的指令接口进行修改。 比如:注意事项&…

阅读更多 →
无法下载Windows系统iso文件 2026/11/18 14:20:46

无法下载Windows系统iso文件

当我遇到这个问题的时候,我打开了一个网站: 登录 然后我打算下载的时候: 突然那个官方的连接就可以下载了:

阅读更多 →
【清华代码熊】DeepSeek V4.1 Flash 后训练详解 2026/11/18 20:01:42

【清华代码熊】DeepSeek V4.1 Flash 后训练详解

📌 上期解析了 DeepSeek V4.1 Flash 模型架构改进,本期解析 DeepSeek V4.1 Flash 预训练/后训练技术: 🌟 预训练:45T 文本 多模态混合语料、直接训练 sparse attention(取消 DeepSeek V4 的 dense 冷启动&…

阅读更多 →
Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ... 2026/11/18 11:04:06

Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ...

文章主要内容和创新点 主要内容 本文聚焦于多模态大语言模型(MLLM)强化学习(RL)训练中的效率问题,提出了一个名为Shuffle-R1的框架。研究发现,当前RL训练存在两个关键缺陷: 优势值坍缩(Advantage Collapsing):批次中大多数优势值集中在零附近,导致有效梯度信号被淹…

阅读更多 →
PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction 2026/11/18 15:55:22

PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction

一、文章主要内容总结 本文聚焦于利用大型语言模型(LLMs)实现个人身份信息(PII)脱敏的研究,旨在解决传统脱敏方法(如基于规则的系统、领域特定命名实体识别(NER)模型)泛化能力差、跨格式/跨语境适应性弱的问题。 研究通过全面评估多种LLM架构(包括密集型LLM(D-LLM…

阅读更多 →
LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model 2026/11/18 21:21:16

LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model

文章主要内容和创新点 主要内容 本文聚焦于二进制图像-文本相关性评估任务(判断图像与文本“相关”或“不相关”),针对该任务中文本格式多样、相关性定义随场景变化等挑战,提出了基于多模态大语言模型(MLLM)的解决方案LLaVA-RE。 模型设计:LLaVA-RE基于LLaVA 1.5架构,…

阅读更多 →

今日资讯

本周资讯

本月资讯

看完文章仍有疑问?

联系尧图顾问,获取一对一建站咨询

立即免费咨询 📞 400-888-8888
📞 ✉