动态规划理论基础和习题【力扣】【算法学习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]); // 不选 + 选
    }
}

后言

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

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

kafka+zookeeper的搭建

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

智象未来(HiDream.ai):从科技创新启程,绘制智能未来新篇章

在人工智能领域飞速演进的当下&#xff0c;智象未来&#xff08;HiDream.ai&#xff09;作为全球领先的多模态生成式人工智能技术供应商&#xff0c;正以其独树一帜的视觉多模态大模型及创新应用&#xff0c;推动行业趋势的前进。智象未来&#xff08;HiDream.ai&#xff09;自…

给电脑加水印的软件有哪些?分享5个快速添加水印的小神器,快来试试!

怎么给电脑加水印呢&#xff1f; 如果一个个手动添加水印&#xff0c;不仅费时费力&#xff0c;还容易出错。那么&#xff0c;有没有更方便快捷的方法呢&#xff1f; 答案是肯定的&#xff01;市面上有许多专门给电脑加水印的软件&#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…

TARE-PLANNER学习记录

参考&#xff1a; CMU-TARE 探索算法官方社区问答汇总_cmu localplanner 部署-CSDN博客 Tare_planner学习笔记_tare planner-CSDN博客 Tare_planner 学习教程(二)_tareplanner-CSDN博客 &#xff08;学习笔记&#xff09;机器人自主导航从零开始第七步——TARE Planner自主…

JMeter基础篇

目录 总目录&#xff1a; 一、JMeter简介&#xff1a; -用途&#xff1a; -优缺点&#xff1a; 二、JMeter安装&#xff1a; 三、项目简介&#xff1a; -学生管理系统&#xff1a; -API接口清单&#xff1a; 查询&#xff1a; 新增&#xff1a; 更新&#xff1a; 删…

AWTK-HarmonyOS NEXT 发布

AWTK 全称为 Toolkit AnyWhere&#xff0c;是 ZLG 倾心打造的一套基于 C 语言开发的 GUI 框架。旨在为用户提供一个功能强大、高效可靠、简单易用、可轻松做出炫酷效果的 GUI 引擎&#xff0c;支持跨平台同步开发&#xff0c;一次编程&#xff0c;到处编译&#xff0c;跨平台使…

右旋圆极化散射后的stocks矢量 与T3矩阵的关系

T3矩阵如下 斯托克斯与T3的关系如下。 斯托克斯与T3均没有平均处理&#xff0c;即斯托克斯是完全极化波的&#xff08;一种琼斯矢量得到&#xff09;&#xff0c;T3是由一个散射矩阵得到&#xff0c;只有一个特征值。

理解 WordPress | 第二篇:结构化分析

WordPress 专题致力于从 0 到 1 搞懂、用熟这种可视化建站工具。 第一阶段主要是理解。 第二阶段开始实践个人博客、企业官网、独立站的建设。 如果感兴趣&#xff0c;点个关注吧&#xff0c;防止迷路。 WordPress 的内容和功能结构可以按照层级来划分&#xff0c;这种层次化的…

Python-利用os,tkinter库编写一个伪恶意程序文件(Pro版)

前言&#xff1a;上一期我们简单学习了如何编写一个多次弹窗警告用户的exe伪恶意文件。我们知道了把Python初始文件编译为exe文件后&#xff0c;程序在没有Python环境的情况下也能正常运行。我们上次编写的程序仅仅只是伪造系统正在执行关机命令前的倒计时的假象&#xff0c;实…

大语言模型训练的全过程:预训练、微调、RLHF

一、 大语言模型的训练过程 预训练阶段&#xff1a;PT&#xff08;Pre training&#xff09;。使用公开数据经过预训练得到预训练模型&#xff0c;预训练模型具备语言的初步理解&#xff1b;训练周期比较长&#xff1b;微调阶段1&#xff1a;SFT&#xff08;指令微调/有监督微调…

字节青训-小S的倒排索引

问题描述 小S正在帮助她的朋友们建立一个搜索引擎。为了让用户能够更快地找到他们感兴趣的帖子&#xff0c;小S决定使用倒排索引。倒排索引的工作原理是&#xff1a;每个单词都会关联一个帖子ID的列表&#xff0c;这些帖子包含该单词&#xff0c;且ID按从小到大的顺序排列。 例…

你需要了解的正则表达式相关知识

正则表达式&#xff08;Regular Expression&#xff0c;简称 regex 或 regexp&#xff09;是一种用于匹配字符串的模式。它广泛应用于文本查找、替换、验证等场景&#xff0c;尤其是在数据处理、网络爬虫、编程等领域非常有用。下面将详细介绍正则表达式的基本语法、常用元字符…

掌握分布式系统的38个核心概念

天天说分布式分布式&#xff0c;那么我们是否知道什么是分布式&#xff0c;分布式会遇到什么问题&#xff0c;有哪些理论支撑&#xff0c;有哪些经典的应对方案&#xff0c;业界是如何设计并保证分布式系统的高可用呢&#xff1f; 1. 架构设计 这一节将从一些经典的开源系统架…

【C++进阶】智能指针的使用和原理(2)

5. shared_ptr和weak_ptr 5.1 shared_ptr循环引用问题 shared_ptr大多数情况下管理资源⾮常合适&#xff0c;⽀持RAII&#xff0c;也⽀持拷贝。但是在循环引⽤的场景下会导致资源没得到释放内存泄漏&#xff0c;所以我们要认识循环引用的场景和资源没释放的原因&#xff0c;并…

【Uniapp】Uniapp Android原生插件开发指北

前言 在uniapp开发中当HBuilderX中提供的能力无法满足App功能需求&#xff0c;需要通过使用Andorid/iOS原生开发实现时&#xff0c;或者是第三方公司提供的是Android的库&#xff0c;这时候可使用App离线SDK开发原生插件来扩展原生能力。 插件类型有两种&#xff0c;Module模…

linux进程的状态之环境变量

我们在前面了解了进程的状态及相关概念 接下来我们接着上一篇进程的状态接着了解环境变量 进程的状态 文章目录 目录 文章目录 前言 二、环境变量 1、常见环境变量 2、查看环境变量 3、修改PATH 4、HOME 5、PATH ​编辑 6、和环境变量相关的命令 三、环境变量的组织…

揭秘集装箱箱号自动识别原理,箱号识别算法

集装箱箱号自动识别算法是一种高效且实用的软件工具。它利用相机、手机或其他摄像头捕获集装箱箱号图像&#xff0c;并通过深度学习的OCR&#xff08;光学字符识别&#xff09;识别技术对集装箱号码进行准确识别。要想进行集装箱箱号识别&#xff0c;需要以下几个基本步骤&…

AndroidLab:一个系统化的Android代理框架,包含操作环境和可复现的基准测试,支持大型语言模型和多模态模型。

2024-10-31&#xff0c;由清华大学和北京大学共同创建的AndroidLab数据集&#xff0c;为安卓自主代理的训练和评估提供了一个包含操作环境、行动空间和可复现基准的系统框架&#xff0c;这对于推动安卓代理技术的发展具有重要意义。 数据集地址&#xff1a;Android Instruct|A…

使用axois自定义基础路径,自动拼接前端服务器地址怎么办

请求路径&#xff1a; http://localhost:5173/http://pcapi-xiaotuxian-front-devtest.itheima.net/home/category/head 很明显多拼接了路径地址 查看基础路径文件发现&#xff1a; //axios基础封装 import axios from axiosconst httpInstance axios.create({baseURL: /h…