动态规划理论基础和习题【力扣】【算法学习day.25】

前言

###我做这类文档一个重要的目的还是给正在学习的大家提供方向(例如想要掌握基础用法,该刷哪些题?)我的解析也不会做的非常详细,只会提供思路和一些关键点,力扣上的大佬们的题解质量是非常非常高滴!!!


习题

1.最后一块石头的重量II

题目链接:1049. 最后一块石头的重量 II - 力扣(LeetCode)

题面:

代码:

class Solution {public int lastStoneWeightII(int[] ss) {int n = ss.length;int sum = 0;for (int i : ss) sum += i;int t = sum / 2;int[][] f = new int[n + 1][t + 1];for (int i = 1; i <= n; i++) {int x = ss[i - 1];for (int j = 0; j <= t; j++) {f[i][j] = f[i - 1][j];if (j >= x) f[i][j] = Math.max(f[i][j], f[i - 1][j - x] + x);}}return Math.abs(sum - f[n][t] - f[n][t]);}
}

2.目标和

题目链接:494. 目标和 - 力扣(LeetCode)

题面:

代码:

class Solution {private int[] nums;private int[][] memo;public int findTargetSumWays(int[] nums, int target) {int s = 0;for (int x : nums) {s += x;}s -= Math.abs(target);if (s < 0 || s % 2 == 1) {return 0;}int m = s / 2; // 背包容量this.nums = nums;int n = nums.length;memo = new int[n][m + 1];for (int[] row : memo) {Arrays.fill(row, -1); // -1 表示没有计算过}return dfs(n - 1, m);}private int dfs(int i, int c) {if (i < 0) {return c == 0 ? 1 : 0;}if (memo[i][c] != -1) { // 之前计算过return memo[i][c];}if (c < nums[i]) {return memo[i][c] = dfs(i - 1, c); // 只能不选}return memo[i][c] = dfs(i - 1, c) + dfs(i - 1, c - nums[i]); // 不选 + 选}
}

后言

上面是动态规划的基本概念和部分习题,下一篇会有其他习题,希望有所帮助,一同进步,共勉!  

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

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

相关文章

Linux的基本指令(一)

1.ls指令 功能&#xff1a;对于目录&#xff0c;该命令列出该目录下的所有子目录与文件。对于文件&#xff0c;将列出文件名以及信息。 常用选项&#xff1a; -a列出目录下的所有文件&#xff0c;包括以 . 开头的隐含文件。 -l列出文件的详细信息 举例&#xff1a; rooti…

智能化健身房管理:Spring Boot与Vue的创新解决方案

作者介绍&#xff1a;✌️大厂全栈码农|毕设实战开发&#xff0c;专注于大学生项目实战开发、讲解和毕业答疑辅导。 &#x1f345;获取源码联系方式请查看文末&#x1f345; 推荐订阅精彩专栏 &#x1f447;&#x1f3fb; 避免错过下次更新 Springboot项目精选实战案例 更多项目…

【Vue】简易博客项目跟做

项目框架搭建 1.使用vue create快速搭建vue项目 2.使用VC Code打开新生成的项目 端口号简单配置 修改vue.config.js文件&#xff0c;内容修改如下 所需库安装 npm install vue-resource --save --no-fund npm install vue-router3 --save --no-fund npm install axios --save …

Hadoop简介及单点伪分布式安装

目录 1. 大数据2. Hadoop简介3. Hadoop伪分布式安装4. Hadoop启动参考 1. 大数据 大数据的定义&#xff1a;一种规模大到在获取、存储、管理、分析方面大大超出传统数据库软件工具能力范围的数据集合。   特征&#xff1a;   1.海量的数据规模   2.快速的数据流转   3.…

windows server2019下载docker拉取redis等镜像并运行项目

一、基本概念 1、windows server 指由微软公司开发的“Windows”系列中的“服务器”版本。这意味着它是基于Windows操作系统的&#xff0c;但专门设计用于服务器环境&#xff0c;而不是普通的桌面或个人用户使用。主要用途包括服务器功能、用户和资源管理、虚拟化等 2、dock…

使用最新版的wvp和ZLMediaKit搭建Gb28181测试服务器

文章目录 说明安装1.安装nodejs简介安装步骤 2.安装java环境3.安装mysql安装修改密码 4.安装redis5.安装编译器6.安装cmake7.安装依赖库8.编译ZLMediaKit9.编译wvp-GB28181-pro 配置1.ZLMediaKit配置2.wvp-GB28181-pro配置2.1.配置ZLMediaKit连接信息2.2.28181服务器的配置2.3.…

Python程序设计 生成器

1. 基础概念 在讲迭代之前&#xff0c;先搞清楚这些名词&#xff1a; 循环&#xff08;loop&#xff09;&#xff0c;指的是在满足条件的情况下&#xff0c;重复执行同一段代码。比如&#xff0c;while 语句。迭代&#xff08;iterate&#xff09;&#xff0c;指的是按照某种…

mac m1 docker本地部署canal 监听mysql的binglog日志

mac m1 docker本地部署canal监听mysql的binglog日志(虚拟机同理) 根据黑马视频部署 1.docker 部署mysql 1.docker拉取mysql 镜像 因为m1是arm架构.需要多加一条信息 正常拉取 docker pull mysql:tagm1拉取 5.7的版本. tag需要自己指定版本 docker pull --platform linux/x…

[linux]docker基础

常见命令 Docker最常见的命令就是操作镜像、容器的命令&#xff0c;详见官方文档: Docker Docs 案例: 查看DockerHub&#xff0c;拉取Nginx镜像&#xff0c;创建并运行Nginx容器 在DockerHub中搜索Nginx镜像 拉取Nginx镜像 查看本地镜像列表 把镜像保持到本地 查看保持命令的…

C++builder中的人工智能(10)神经网络中的Sigmoid函数

在这篇文章中&#xff0c;我们将探讨最受欢迎的激活函数之一——Sigmoid函数。我们将解释什么是Logistic函数&#xff0c;以及它与Sigmoid函数的区别&#xff0c;并展示如何在C应用中使用这些函数。 目录 人工神经网络&#xff08;ANN&#xff09;中的激活函数是什么&#xff…

cursor:如何注销帐号和使用流量

点击右上角的设定图标 点击管理 在弹出的网页点登入 点”continue" 点SETING 了解最新信息请扫码关注&#xff1a;

如何选择适合小团队的项目管理工具?免费与开源软件推荐

目录 一、小团队项目管理工具的重要性 二、热门项目管理工具介绍 &#xff08;一&#xff09;禅道 &#xff08;二&#xff09;Trello &#xff08;三&#xff09;Asana &#xff08;四&#xff09;JIRA 三、免费项目管理软件推荐 &#xff08;一&#xff09;ES 管理器 …

Scaffold-ETH 2:颠覆传统开发的区块链神器,快速构建你的去中心化应用!

目录 引言一、Scaffold-eth框架二、前期准备三、搭建Scaffold-ETH 2&#xff08;一&#xff09;使用npx create-ethlatest进行设置&#xff08;二&#xff09;使用git clone进行设置1、克隆仓库&#xff1a;2、进入到此目录3、安装依赖项 四、配置Scaffold ETH-2的开发环境&…

kafka+zookeeper的搭建

kafka从2.8版本开始&#xff0c;就可以不用配置zookeeper了&#xff0c;但是也可以继续配置。我目前使用的kafka版本是kafka_2.12-3.0.0.tgz&#xff0c;其中前面的2.12表示是使用该版本的scala语言进行编写的&#xff0c;而后面的3.00才是kafka当前的版本。 通过百度网盘分享…

恢复rm -rf删除的数据

注&#xff1a;本文演示的是ext4文件系统格式数据恢复 系统版本&#xff1a;ubuntu16.04 恢复数据目录&#xff1a;数据盘&#xff08;非根&#xff09;目录 恢复工具&#xff1a;extundelete 0.2.4 恢复所有被删除数据 ext4magic 恢复指定目录数据 一、注意事项&#xff1a; …

Elasticsearch(三):Elasticvue使用及DSL执行新增、查询操作

Elasticvue使用及DSL执行CURD 1 概述2 什么是Elasticsearch DSL3 基本结构4 客户端工具介绍4.1 索引介绍4.2 创建简单索引4.3 创建相对完整的索引4.4 插入数据4.4.1 基本插入操作4.4.2 批量插入操作 5 常用的DSL查询类型5.1 match查询5.1.1 match工作原理5.1.2 operator 参数5.…

静态库、动态库、framework、xcframework、use_frameworks!的作用、关联核心SDK工程和测试(主)工程、设备CPU架构

1.1库的概念 库&#xff1a;程序代码的集合&#xff0c;编译好的二进制文件加上头文件供使用&#xff0c;共享程序代码的一种方式。 1.2库的分类 根据开源情况分为&#xff1a;开源库&#xff08;能看到具体实现&#xff09;、闭源库&#xff08;只公开调用的的接口&#xf…

C++【string类,模拟实现string类】

&#x1f31f;个人主页&#xff1a;落叶 &#x1f31f;当前专栏: C专栏 目录 为什么学习string类 C语言中的字符串 标准库中的string类 auto和范围for auto关键字 迭代器 范围for string类的常用接口说明和使用 1. string类对象的常见构造 2.string类对象的容量操作 3…

Me-LLaMA——用于医疗领域的新型开源大规模语言模型

摘要 大规模语言模型的出现是提高病人护理质量和临床操作效率的一个重大突破。大规模语言模型拥有数百亿个参数&#xff0c;通过海量文本数据训练而成&#xff0c;能够生成类似人类的反应并执行复杂的任务。这在改进临床文档、提高诊断准确性和管理病人护理方面显示出巨大的潜…

关于在VS中使用Qt不同版本报错的问题

最开始需要配置的地方 首先看一下我的Qt有关的环境变量&#xff1a; Path环境变量里&#xff1a; 这里就是把对应Qt编译器环境下的bin目录放进来&#xff1a;比如你使用的是msvc2017_64或者MinGW QMAKESPEC环境变量&#xff1a; 这个就选择Qt对应的编译器目录下的\mkspecs\w…