leetcode day10 动态规划篇 64+139

64 最小路径和

给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

说明:每次只能向下或者向右移动一步。

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 200

解题思路:动态规划题步骤

dp[i][j]表示到i行j列最小路径和

1、初始化,dp[i][j]=grid[i-1][j-1]

只有一条路径的,即图形左边缘和上边缘,初始化。

 dp[i][1]+=grid[j][0]

  dp[1][i]+=grid[0][j]

3、确定状态转移方程

dp[i][j]=min(dp[i][j-1],dp[i-1][j])+dp[i][j]

int min(int a,int b){if(a>b)return b;else return a;
}
int minPathSum(int** grid, int gridSize, int* gridColSize) {//m为行,n为列int m=gridSize,n=gridColSize[0];if(m==0||n==0)return 0;int dp[205][205]={};//初始化for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){dp[i][j]=grid[i-1][j-1];}}for(int i=2;i<=m;i++){for(int j=0;j<i-1;j++){dp[i][1]+=grid[j][0];}}for(int i=2;i<=n;i++){for(int j=0;j<i-1;j++){dp[1][i]+=grid[0][j];}}//确定状态转移方程for(int i=2;i<=m;i++){for(int j=2;j<=n;j++){dp[i][j]=min(dp[i][j-1],dp[i-1][j])+dp[i][j];}}return dp[m][n];
}

139 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true

注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。

示例 1:

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2:

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。注意,你可以重复使用字典中的单词。

示例 3:

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

解题思路:动态规划

dp[i]=1表示前i个来自字典,Size[i]为字典中第i个单词的长度

1、初始化 dp[0]=1,其他为0

2、确定状态转移方程

i从1开始,那么k=i-1+Size[j]

dp[k]=dp[k]||(dp[i-1]&&strncmp(s+i-1,wordDict[j],Size[j])==0)

strcmp与strncmp都是用来比较字符串的,区别在于能否比较指定长度字符串,故要多传一个长度参数。头文件为<string.h>

——举个例子 leetcode 字典为leet code

Size[0]=4,Size[1]=4

i=1,j=0,k=4,dp[4]=dp[0]&&strncmp(s,wordDict[0],Size[0]==0)=1

i=2,j=0,k=5,dp[5]=dp[1]&&strncmp(s+1,wordDict[0],Size[0]==0)=0

……

i=5,j=0,k=8,dp[8]=dp[4]&&strncmp(s+4,wordDict[0],Size[0]==0)=0

i=5,j=0,k=8,dp[8]=dp[4]&&strncmp(s+4,wordDict[1],Size[1]==0)=1

所以dp[8]=1=true

思考:如果字典中的单词不能重复使用,该怎么做

可以设个标记flag数组,如果字典第i个单词用过,即dp[k]=1时,标记flag[j]为1。

j循环中,当flag[j]==0时才使用下面的步骤

bool wordBreak(char * s, char ** wordDict, int wordDictSize){int len=strlen(s),i,j;if(wordDictSize==0)return 0;int Size[wordDictSize]={};for(i=0;i<wordDictSize;i++)Size[i]=strlen(wordDict[i]);//dp[i]=1表示前i个来自字典int dp[len+1];dp[0]=1;for(i=1;i<=len;i++)dp[i]=0;for(i=1;i<=len;i++){for(j=0;j<wordDictSize;j++){int k=i-1+Size[j];if(k>len)continue;dp[k]=dp[k]||(dp[i-1]&&strncmp(s+i-1,wordDict[j],Size[j])==0);}}return dp[len];
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/469429.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Flutter 小技巧之 Shader 实现酷炫的粒子动画

在之前的《不一样的思路实现炫酷 3D 翻页折叠动画》我们其实介绍过&#xff1a;如何使用 Shader 去实现一个 3D 的翻页效果&#xff0c;具体就是使用 Flutter 在 3.7 开始提供 Fragment Shader API &#xff0c;因为每个像素都会过 Fragment Shader &#xff0c;所以我们可以通…

SpringCloud框架学习(第二部分:Consul、LoadBalancer和openFeign)

目录 六、Consul服务注册和发现 1.基本介绍 2.下载运行 3.服务注册与发现 &#xff08;1&#xff09;支付服务provider8001注册进consul &#xff08;2&#xff09;修改订单服务cloud-consumer-order80 4.CAP &#xff08;1&#xff09;CAP理论 &#xff08;2&#x…

大数据学习12之HBase

1.基本概念 1.1简介 Apache HBase&#xff08;Hadoop DataBase&#xff09;是一个开源的、高可靠性、高性能、面向列&#xff08;这里指列族&#xff0c;非列式存储&#xff09;、可伸缩、实时读写的分布式数据库&#xff0c;其设计思想来源于 Google 的 BigTable 论文。利用 …

el-input 正则表达式校验输入框不能输入汉字

<el-form :model"data1" :rules"rules" ref"ruleForm" label-width"210px" class"demo-ruleForm"><el-form-item label"锯路&#xff1a;" prop"sawKref"><el-input class"inptWid…

linux rocky 9.4部署和管理docker harbor私有源

文章目录 Harbor简介安装Harbor技术细节1.安装系统(略),设置主机名和IP2.安装docker3.安装docker-compose4.安装Harbor私有源仓库5 测试登录1.本机登录2.客户端登录Harbor服务器配置docker源1. 下载镜像2.把镜像上传到Harbor私有仓库源3.客户端下载镜像,并且启动容器linux …

03WIFI与蓝牙1——基于全志V3S的Linux开发板教程笔记

1. Kernel支持 1&#xff09;配置 终端输入&#xff1a; make menuconfig使能如下部分&#xff1a; 2&#xff09;编译 保存并退出后编译内核&#xff1a; make licheepi_zero_defconfig make menuconfig #配置内核&#xff0c;有需要的话配置 make -j16 make -j16 modu…

iOS 18.2 重磅更新:6个大动作

根据外媒报道&#xff0c;iOS 18.2迎来重磅更新&#xff0c;将带来6个大动作&#xff0c;这是一次非常实用的更新。不过要注意的是&#xff0c;其中涉及到AI的功能&#xff0c;国行iPhone 暂时还不可用&#xff0c;只能等审核通过了。 1&#xff0c;Safari下载进度 过去通过S…

【单例模式】饿汉式与懒汉式以及线程安全

1. 单例模式介绍 饿汉式单例模式&#xff1a;还没有获取实例对象&#xff0c;实例对象就已经产生了。一定是线程安全的。 懒汉式单例模式&#xff1a;需要用的时候再构造实例。 应用场景&#xff1a;比如日志模块&#xff0c;数据库模块&#xff0c;开发的解析器模块。 2.饿…

一文了解 Tableau 2024.3 如何展现已发布数据源的数据模型

通过减少数据源的重复建设&#xff0c;提高数据透明度&#xff0c;可组合数据源将为企业带来更高的数据利用效率 在 TC24 用户大会上&#xff0c;Tableau 产品团队提出了一个非常重要的功能概念——可组合的数据源。这意味着你将很快能够对 Tableau 已发布的数据源进行连接、关…

Unity 网格模型及优化

一个模型中可以包含很多网格&#xff0c;一个模型可以由多个网格组成。在Unity3D中一个网格可以由多个子网格&#xff08;Sub-Mesh)组成。 在渲染引擎的时候&#xff0c;每个子网格都要匹配一个材质球来做渲染&#xff0c;实际上一个子网格本身就是一个个普通的模型&#xff0…

第四十三章 Vue之mapMutations简化mutations操作

目录 一、引言 二、完整代码 2.1. App.vue 2.2. main.js 2.3. Son1.vue 2.4. Son2.vue 2.5. index.js 一、引言 本章节我们通过掌握辅助函数mapMutations&#xff0c;来简化前面章节中调用mutations函数的繁琐方式。mapMutations 和 mapState很像&#xff0c;它是把位于…

【论文复现】ChatGPT多模态命名实体识别

&#x1f4dd;个人主页&#x1f339;&#xff1a;Eternity._ &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; ❀ChatGPT ChatGPT辅助细化知识增强&#xff01;1. 研究背景2. 模型结构和代码3. 任务流程第一阶段&#xff1a;辅助精炼知识启发式生成第二阶段…

echarts-gl 3D柱状图配置

1. 源码 此demo可以直接在echarts的编辑器中运行 option {title: {text: 产量图,textStyle: {color: rgba(255, 255, 255, 1),fontSize: 17},left: center},tooltip: {},legend: {show: false,orient: vertical,x: left,top: 0,right: 20,textStyle: {fontSize: 12}},visualM…

c语言数据结构与算法--简单实现栈和队列的出栈与入栈

&#xff08;一&#xff09;栈的基本概念 栈(Stack)是限定仅在表尾进行插入和删除操作的线性表&#xff0c;如铁路调度。如下 图&#xff1a; &#xff08;二&#xff09;栈的的表现形式 栈有两种表示形式&#xff1a;栈的表示和实现、栈的 链式表示。 1&#xff0e;栈的表示…

人工智能(AI)和机器学习(ML)技术学习流程

目录 人工智能(AI)和机器学习(ML)技术 自然语言处理(NLP): Word2Vec: Seq2Seq(Sequence-to-Sequence): Transformer: 范式、架构和自注意力: 多头注意力: 预训练、微调、提示工程和模型压缩: 上下文学习、思维链、全量微调、量化、剪枝: 思维树、思维…

C++初阶——vector

一、什么是vector vector是表示可变大小的数组的序列容器&#xff0c;就像数组一样&#xff0c;vector也采用连续空间来存储元素。也就是说它的访问和数组一样高效&#xff0c;但是它的大小是动态可变的&#xff0c;并且它的大小会被容器自动处理。 二、vector的构造 常用的构…

移远通信亮相骁龙AI PC生态科技日,以领先的5G及Wi-Fi产品革新PC用户体验

PC作为人们学习、办公、娱乐的重要工具&#xff0c;已经深度融入我们的工作和生活。随着物联网技术的快速发展&#xff0c;以及人们对PC性能要求的逐步提高&#xff0c;AI PC成为了行业发展的重要趋势。 11月7-8日&#xff0c;骁龙AI PC生态科技日在深圳举办。作为高通骁龙的重…

AIGC专栏17——EasyAnimate V5版本详解 应用MMDIT结构,拓展模型规模到12B 支持不同控制输入的控制模型

AIGC专栏17——EasyAnimate V5版本详解 应用MMDIT结构&#xff0c;拓展模型规模到12B 支持不同控制输入的控制模型 学习前言相关地址汇总源码下载地址HF测试链接 测试效果Image to VideoText to Video EasyAnimate详解技术储备Diffusion Transformer (DiT)Stable Diffusion 3Co…

Android Studio | 最新版本配置要求高,JDK运行环境不适配,导致无法启动App

Android Studio 的最新版本配置要求比较高&#xff0c;这时候需要降低插件的版本&#xff0c;才能正常启动项目 build.gradle 文件的 dependencies 部分中&#xff0c;使用 libs 作为一些常用库的别名。这些别名在项目的 gradle.properties 文件或者某个特定的 versions.prope…

ssm093基于Java Web的毕业生就业状况管理系统设计与实现+jsp(论文+源码)_kaic

毕 业 设 计&#xff08;论 文&#xff09; 题目&#xff1a;毕业生就业状况管理系统设计与实现 摘 要 现代经济快节奏发展以及不断完善升级的信息化技术&#xff0c;让传统数据信息的管理升级为软件存储&#xff0c;归纳&#xff0c;集中处理数据信息的管理方式。本毕业生就业…