目标和问题:从回溯到动态规划的旅程

目录

引言

题目描述

示例

初步思路:回溯法

回溯法实现

分析

转变思路:动态规划

问题转换

状态定义

状态转移方程

二维动态规划实现

压缩到一维动态规划

一维动态规划实现

详细讲解:从回溯到动态规划的旅程

1. 从回溯到动态规划的转变

2. 问题转换的关键

3. 状态定义与转移

4. 压缩到一维的优化

二维动态规划

一维动态规划

举例说明

从后往前遍历

从前往后遍历

总结

总结


引言

算法学习之路充满了挑战和乐趣,其中背包问题更是经典中的经典。今天,我们一起探讨一道有趣的题目——“目标和”,看一看它如何从回溯变身为动态规划。

494. 目标和 - 力扣(LeetCode)

题目描述

给定一个非负整数数组 nums 和一个整数 target。我们可以向数组中的每个整数前添加 '+' 或 '-',然后把它们串联起来形成表达式。我们的任务是找出所有可能的表达式,使其结果等于 target

示例

输入:nums = [1, 1, 1, 1, 1], target = 3
输出:5
解释:一共有 5 种方法让最终目标和为 3。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

初步思路:回溯法

第一眼看到这道题,或许你会想用回溯法。没错,这也是大多数人的第一反应:通过递归地添加 '+' 或 '-' 来尝试所有可能的表达式。

回溯法实现

class Solution {int result = 0;public int findTargetSumWays(int[] nums, int target) {if (nums.length == 0) return 0;backtrack(nums, 0, target);return result;}void backtrack(int[] nums, int i, int remain) {if (i == nums.length) {if (remain == 0) {result++;}return;}backtrack(nums, i + 1, remain - nums[i]);backtrack(nums, i + 1, remain + nums[i]);}
}

分析

回溯法通过递归地尝试每一种可能的组合,最终统计满足条件的组合数目。虽然直观,但时间复杂度为 O(2^n),在输入规模较大时效率较低。

转变思路:动态规划

接下来,我们将这道题转换为动态规划的问题。这里有一个巧妙的转换,让我们一起来看。

问题转换

其实,这个问题可以转化为一个子集划分问题,而子集划分问题又是一个典型的背包问题

首先,如果我们把 nums 划分成两个子集 A 和 B,分别代表分配 + 的数和分配 - 的数,那么他们和 target 存在如下关系:

sum(A) - sum(B) = target
sum(A) = target + sum(B)
sum(A) + sum(A) = target + sum(B) + sum(A)
2 * sum(A) = target + sum(nums)

我们可以将问题转换为找到两个子集,使得一个子集和为 (sum + target) / 2,另一个子集和为 sum - (sum + target) / 2,其中 sum 是数组 nums 的总和。

状态定义

  • 定义 dp[i][j] 表示使用前 i 个数字,是否可以组成和为 j 的子集数。

状态转移方程

  • 如果不使用当前数字 nums[i-1],即 dp[i][j] = dp[i-1][j]

  • 如果使用当前数字 nums[i-1],即 dp[i][j] = dp[i-1][j-nums[i-1]](前提是 j >= nums[i-1]

二维动态规划实现

int findTargetSumWays(int[] nums, int target) {int sum = 0;for (int n : nums) sum += n;// 这两种情况,不可能存在合法的子集划分if (sum < Math.abs(target) || (sum + target) % 2 == 1) {return 0;}return subsets(nums, (sum + target) / 2);
}int subsets(int[] nums, int sum) {int n = nums.length;int[][] dp = new int[n + 1][sum + 1];dp[0][0] = 1; // 初始状态,和为 0 的子集只有一个,即空集for (int i = 1; i <= n; i++) {for (int j = 0; j <= sum; j++) {if (j >= nums[i-1]) {dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];} else {dp[i][j] = dp[i-1][j];}}}return dp[n][sum];
}

压缩到一维动态规划

为了进一步优化空间复杂度,我们可以将二维数组压缩到一维数组。

对照二维 dp,只要把 dp 数组的第一个维度全都去掉就行了,唯一的区别就是这里的 j 要从后往前遍历,原因如下

因为二维压缩到一维的根本原理是,dp[j] 和 dp[j-nums[i-1]] 还没被新结果覆盖的时候,相当于二维 dp 中的 dp[i-1][j] 和 dp[i-1][j-nums[i-1]]

那么,我们就要做到:在计算新的 dp[j] 的时候,dp[j] 和 dp[j-nums[i-1]] 还是上一轮外层 for 循环的结果

如果你从前往后遍历一维 dp 数组,dp[j] 显然是没问题的,但是 dp[j-nums[i-1]] 已经不是上一轮外层 for 循环的结果了,这里就会使用错误的状态,当然得不到正确的答案。

也就是说。在将二维动态规划压缩到一维动态规划时,需要确保在计算新的 dp[j] 时,dp[j]dp[j - nums[i-1]] 不会在本轮内循环中被更新。这就是为什么我们在一维动态规划中需要从后往前遍历的原因。

一维动态规划实现

int findTargetSumWays(int[] nums, int target) {int sum = 0;for (int n : nums) sum += n;// 这两种情况,不可能存在合法的子集划分if (sum < Math.abs(target) || (sum + target) % 2 == 1) {return 0;}return subsets(nums, (sum + target) / 2);
}/* 计算 nums 中有几个子集的和为 sum */
int subsets(int[] nums, int sum) {int n = nums.length;int[] dp = new int[sum + 1];// base casedp[0] = 1;for (int i = 1; i <= n; i++) {// j 要从后往前遍历for (int j = sum; j >= 0; j--) {// 状态转移方程if (j >= nums[i-1]) {dp[j] = dp[j] + dp[j-nums[i-1]];} else {dp[j] = dp[j];}}}return dp[sum];
}

详细讲解:从回溯到动态规划的旅程

1. 从回溯到动态规划的转变

最初的回溯法思路简单直观,但其时间复杂度为 O(2^n),在处理大规模数据时效率低下。为了提高效率,我们需要找到一种方法,将其转变为动态规划问题。

2. 问题转换的关键

通过将问题转换为背包问题,我们引入了动态规划的思想。具体来说,我们将问题转化为寻找两个子集,使得其中一个子集和为 (sum + target) / 2

3. 状态定义与转移

  • 状态定义dp[i][j] 表示使用前 i 个数字,是否可以组成和为 j 的子集数。

  • 状态转移方程:通过递推关系,逐步求解子问题,从而解决原问题。

4. 压缩到一维的优化

为了进一步优化空间复杂度,我们将二维动态规划压缩到一维动态规划。这一过程的关键在于从后往前更新数组,确保在计算新的 dp[j] 时,dp[j]dp[j - nums[i]] 仍然是上一轮的结果,避免状态覆盖问题。

二维动态规划

在二维动态规划中,状态转移方程是: [ dpi = dpi-1 + dpi-1] ]

这个方程表明:

  • dp[i][j] 是在第 i 轮计算的。

  • dp[i-1][j]dp[i-1][j-nums[i-1]] 都是上一轮(即第 i-1 轮)计算的结果。

一维动态规划

在一维动态规划中,状态转移方程是: [ dp[j] = dp[j] + dp[j-nums[i]] ]

为了确保在计算新的 dp[j] 时,dp[j]dp[j - nums[i]] 都是上一轮的结果,我们需要从后往前遍历 dp 数组。这样可以保证 dp[j - nums[i]] 在当前轮次还没有被更新。

举例说明

假设 nums = [1, 2, 3]sum = 4

从后往前遍历
  1. 初始化

    dp = [1, 0, 0, 0, 0]
  2. 遍历 nums[0] = 1

    for (int j = 4; j >= 1; j--) {dp[j] += dp[j - 1];
    }

    更新后:

    dp = [1, 1, 0, 0, 0]
  3. 遍历 nums[1] = 2

    for (int j = 4; j >= 2; j--) {dp[j] += dp[j - 2];
    }

    更新后:

    dp = [1, 1, 1, 1, 0]
  4. 遍历 nums[2] = 3

    for (int j = 4; j >= 3; j--) {dp[j] += dp[j - 3];
    }

    更新后:

    dp = [1, 1, 1, 2, 1]
从前往后遍历
  1. 初始化

    dp = [1, 0, 0, 0, 0]
  2. 遍历 nums[0] = 1

    for (int j = 1; j <= 4; j++) {dp[j] += dp[j - 1];
    }

    更新后:

    dp = [1, 1, 1, 1, 1]
  3. 遍历 nums[1] = 2

    for (int j = 2; j <= 4; j++) {dp[j] += dp[j - 2];
    }

    更新后:

    dp = [1, 1, 2, 2, 2]
  4. 遍历 nums[2] = 3

    for (int j = 3; j <= 4; j++) {dp[j] += dp[j - 3];
    }

    更新后:

    dp = [1, 1, 2, 3, 3]

通过对比可以看出,从前往后遍历会导致在当前轮次中使用已经更新过的 dp[j - nums[i]],从而得到错误的结果。而从后往前遍历可以确保在计算新的 dp[j] 时,dp[j]dp[j - nums[i]] 都是上一轮的结果。

总结
  • 从后往前遍历:确保在计算新的 dp[j] 时,dp[j]dp[j - nums[i]] 仍然是上一轮循环的结果,避免在当前轮次中使用已更新的值。

  • 从前往后遍历:可能会使用当前轮次已经更新的 dp[j - nums[i]],导致错误的结果。

希望这个解释能够帮助你更好地理解为什么在一维动态规划中需要从后往前遍历。如果还有任何问题,请随时告诉我!

总结

通过这道“目标和”问题,我们展示了如何从回溯法转换为动态规划。这不仅提高了算法的效率,也拓宽了我们的思路。在算法的世界里,转换思维方式,寻求优化方案,是解决复杂问题的重要手段。

希望这篇博客能够帮助你理解背包问题的变种及其动态规划的应用。如果你有任何问题或建议,欢迎在评论区留言。

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

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

相关文章

【java计算机毕设】美容院管理系统 项目源代码MySQL springboot vue html maven+文档 前后端可分离也可不分离

目录 1项目功能 2项目介绍 3项目地址 1项目功能 【java计算机毕设】美容院管理系统 项目源代码MySQL springboot vue html maven文档 前后端可分离也可不分离 2项目介绍 系统功能&#xff1a; 美容院管理系统包括管理员、用户俩种角色。 管理员功能包括个人中心模块用于修改…

YOLO-letter box

最细致讲解yolov8模型推理完整代码--&#xff08;前处理&#xff0c;后处理&#xff09; - 博客-中国极客 (chinageek.org) 直接用resize&#xff0c;图片会变形&#xff0c;宽高比会不对 letterbox函数就是把图片弄到想要的大小&#xff0c;保持宽高比&#xff0c;然后少掉的部…

数字媒体技术基础之:DNG 文件

DNG&#xff08;Digital Negative&#xff09;文件是一种用于存储原始图像数据的文件格式&#xff0c;由 Adobe Systems 于2004年开发并推广。DNG 是一种开放的、非专利的原始图像格式&#xff0c;旨在为不同相机制造商提供一个统一的存储格式。DNG 文件保存了原始的、未处理的…

【Linux】线程id与互斥(线程三)

上一期我们进行了线程控制的了解与相关操作&#xff0c;但是仍旧有一些问题没有解决 本章第一阶段就是解决tid的问题&#xff0c;第二阶段是进行模拟一个简易线程库&#xff08;为了加深对于C库封装linux原生线程的理解&#xff09;&#xff0c;第三阶段就是互斥。 目录 线程id…

Python-数据分析组合可视化实例图【附完整源码】

数据分析组合可视化实例图 开篇&#xff1a;应女朋友的要求&#xff0c;于是写下了这篇详细的数据可视化代码及完整注释 一&#xff1a;柱状图、折线图横向组合网格布局 本段代码使用了pyecharts库来创建一个包含多个图表&#xff08;柱状图、折线图&#xff09;和网格布局的…

鸿蒙应用更新跳转到应用市场

鸿蒙没有应用下载安装&#xff0c;只支持跳转到应用市场更新 gotoMarket(){try {const request: Want {parameters: {// 此处填入要加载的应用包名&#xff0c;例如&#xff1a; bundleName: "com.huawei.hmsapp.appgallery"bundleName: com.huawei.hmos.maps.app}}…

【NOI-题解】1372. 活动选择1456. 淘淘捡西瓜1485. 接水问题

文章目录 一、前言二、问题问题&#xff1a;1372. 活动选择问题&#xff1a;1456. 淘淘捡西瓜问题&#xff1a;1485. 接水问题 三、感谢 一、前言 本章节主要对贪心问题进行讲解&#xff0c;包括《1372. 活动选择》《1456. 淘淘捡西瓜》《1485. 接水问题》题目。 二、问题 问…

Debian linux安装最新版Cmake

直接sudo apt install camke不是最新版本 卸载cmake sudo apt autoremove cmake下载cmake cmake官网 最上面的是候选版本&#xff0c;往下滑是最新稳定版 解压&#xff08;改成自己的包&#xff09; tar -zxvf cmake-3.30.0-rc4.tar.gz进入解压后的文件夹 lscd cmake-3.3…

【项目实践】贪吃蛇

一、游戏效果展示二、博客目标三、使用到的知识四、Win32 API 介绍 4.1 WIn32 API4.2 控制台程序4.3 控制屏幕上的坐标COORD4.4 GetStdHandle4.5 GetConsoleCursorInfo 4.5.1 CONSOLE_CURSOR_INFO 4.6 SetConsoleCursorInfo4.7 SetConsoleCursorPosition4.8 GetAsyncKeyState 五…

Python 项目依赖离线管理 pip + requirements.txt

背景 项目研发环境不支持联网&#xff0c;无法通过常规 pip install 来安装依赖&#xff0c;此时需要在联网设备下载依赖&#xff0c;然后拷贝到离线设备进行本地安装。 两台设备的操作系统、Python 版本尽可能一致。 离线安装依赖 # 在联网设备上安装项目所需的依赖 # -d …

Unity射击游戏开发教程:(29)躲避敌人的子弹射击

在这篇文章中,我将介绍如何创建一个可以使玩家火力无效的敌人。创建的行为如下...... 当玩家向敌人开火时,敌人会向左或向右移动。向左或向右的移动是随机选择的,并在一段时间后停止敌人的移动。如果敌人移出屏幕,它就会绕到另一边。将一个精灵拖到画布上,将其缩小以匹配游…

03.C1W2.Sentiment Analysis with Naïve Bayes

目录 Probability and Bayes’ RuleIntroductionProbabilitiesProbability of the intersection Bayes’ RuleConditional ProbabilitiesBayes’ RuleQuiz: Bayes’ Rule Applied Nave Bayes IntroductionNave Bayes for Sentiment Analysis P ( w i ∣ c l a s s ) P(w_i|clas…

基于RK3588的GMSL、FPDLink 、VByone及MIPI等多种摄像模组,适用于车载、机器人工业图像识别领域

机器人&工业摄像头 针对机器人视觉与工业检测视觉&#xff0c;信迈自主研发和生产GMSL、FPDLink 、VByone及MIPI等多种摄像模组&#xff0c;并为不同应用场景提供多种视场角度和镜头。拥有资深的图像算法和图像ISP专家团队&#xff0c;能够在软件驱动层开发、ISP算法、FPG…

【C#】找不到属性集方法。get只读属性用了反射设置setValue肯定报错

欢迎来到《小5讲堂》 这是《C#》系列文章&#xff0c;每篇文章将以博主理解的角度展开讲解。 温馨提示&#xff1a;博主能力有限&#xff0c;理解水平有限&#xff0c;若有不对之处望指正&#xff01; 背景 找不到属性集方法。get只读属性用了反射设置setValue肯定报错 报错…

ffmpeg下载/配置环境/测试

一、下载 1、访问FFmpeg官方网站下载页面&#xff1a;FFmpeg Download Page&#xff1b; 2、选择适合Windows的版本&#xff08;将鼠标移动到windows端&#xff09;。通常&#xff0c;你会找到“Windows builds from gyan.dev”或者“BtbN GitHub Releases”等选项&#xff0…

私域和社群的差别是什么?

社群就是拉很多人建群就可以了&#xff0c;但是私域不是&#xff0c;这里有三点不同 1、私域的用户来源&#xff0c;不仅仅是微信&#xff0c;而是基于一定的联系形成的链接&#xff0c;比如买了商家的货&#xff0c;反复购买觉得好&#xff0c;推荐给亲朋好友的二次开发用户&…

探讨4层代理和7层代理行为以及如何获取真实客户端IP

准备工作 实验环境 IP角色192.168.1.100客户端请求IP192.168.1.100python 启动的HTTP服务192.168.1.102nginx服务192.168.1.103haproxy 服务 HTTP服务 这是一个简单的HTTP服务&#xff0c;主要打印HTTP报文用于分析客户端IP #!/usr/bin/env python # coding: utf-8import …

java-数据结构与算法-02-数据结构-02-链表

文章目录 1. 概述2. 单向链表3. 单向链表&#xff08;带哨兵&#xff09;4. 双向链表&#xff08;带哨兵&#xff09;5. 环形链表&#xff08;带哨兵&#xff09;6. 习题E01. 反转单向链表-Leetcode 206E02. 根据值删除节点-Leetcode 203E03. 两数相加-Leetcode 2E04. 删除倒数…

C++必修:深入理解继承与虚继承

✨✨ 欢迎大家来到贝蒂大讲堂✨✨ &#x1f388;&#x1f388;养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; 所属专栏&#xff1a;C学习 贝蒂的主页&#xff1a;Betty’s blog 1. 继承的概念与定义 1.1. 继承的概念 继承(inheritance)机制是面向对象程序设计…

上位机网络通讯

目录 一 设计原型 二 后台源码 一 设计原型 二 后台源码 using System; using System.Net.Sockets; using System.Text; using System.Threading.Tasks; using System.Windows.Forms;namespace 上位机网络通讯 {public partial class Form1 : Form{public Form1(){Initializ…