蓝桥杯练习题——dp

五部曲(代码随想录)

1.确定 dp 数组以及下标含义
2.确定递推公式
3.确定 dp 数组初始化
4.确定遍历顺序
5.debug

入门题

1.斐波那契数

在这里插入图片描述

思路

1.f[i]:第 i 个数的值
2.f[i] = f[i - 1] + f[i - 2]
3.f[0] = 0, f[1] = 1
4.顺序遍历
5.记得特判 n == 0 的时候,因为初始化了 f[1]

class Solution {
public:int fib(int n) {if(n == 0) return n;vector<int> f(n + 1);f[0] = 0, f[1] = 1;for(int i = 2; i <= n; i++) f[i] = f[i - 1] + f[i - 2];return f[n];}
};

2.爬楼梯

在这里插入图片描述

思路

每次可以从下面一个台阶或者下面两个台阶处上来

1.f[i]:爬到第 i 阶楼梯有多少种方法
2.f[i] = f[i - 1] + f[i - 2]
3.f[0] = 1, f[1] = 1
4.顺序遍历

class Solution {
public:int climbStairs(int n) {vector<int> f(n + 1);f[0] = 1, f[1] = 1;for(int i = 2; i <= n; i++) f[i] = f[i - 1] + f[i - 2];return f[n];}
};

3.使用最小花费爬楼梯

在这里插入图片描述

思路

可以从 0 或 1 处开始爬楼梯,需要爬到第 n 阶楼梯

1.f[i]:爬到第 i 阶楼梯需要的最小花费
2.f[i] = min(f[i - 1] + cost[i - 1], f[i - 2] + cost[i - 2)
3.f[0] = 0, f[1] = 0
4.顺序遍历

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();vector<int> f(n + 1);f[0] = 0, f[1] = 0;for(int i = 2; i <= n; i++){f[i] = min(f[i - 1] + cost[i - 1], f[i - 2] + cost[i - 2]);}return f[n];}
};

4.不同路径

在这里插入图片描述

思路

1.f[i][j]: 走到 (i, j) 总共的路径
2.f[i][j] = f[i - 1][j] + f[i][j - 1]
3.f[i][1] = 1, f[1][i] = 1
4.顺序遍历

class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> f(n + 1, vector<int>(m + 1));for(int i = 0; i <= n; i++) f[i][1] = 1;for(int i = 0; i <= m; i++) f[1][i] = 1;for(int i = 2; i <= n; i++){for(int j = 2; j <= m; j++){f[i][j] = f[i - 1][j] + f[i][j - 1];}}return f[n][m];}
};

5.不同路径 II

在这里插入图片描述

思路

1.f[i][j]: 走到 (i, j) 总共的路径
2.f[i][j] = f[i - 1][j] + f[i][j - 1]
3.f[i][0] = 1, f[0][i] = 1, 其他 = 0
4.顺序遍历

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int n = obstacleGrid.size();int m = obstacleGrid[0].size();vector<vector<int>> f(n, vector<int>(m, 0));for(int i = 0; i < n && !obstacleGrid[i][0]; i++) f[i][0] = 1;for(int i = 0; i < m && !obstacleGrid[0][i]; i++) f[0][i] = 1;for(int i = 1; i < n; i++){for(int j = 1; j < m; j++){if(!obstacleGrid[i][j]){f[i][j] = f[i - 1][j] + f[i][j - 1];}}}return f[n - 1][m - 1];}
};

6.整数拆分

在这里插入图片描述

思路

1.f[i]: 拆数字 i 可得到的最大乘积
2.拆分成 j * (i - j) 或 j * f[i - j],f[i] = max(f[i], max(j * (i - j), j * [i - j]))
3.f[0] = 0, f[1] = 1
4.顺序遍历

class Solution {
public:int integerBreak(int n) {vector<int> f(n + 1);f[0] = 0, f[1] = 1;for(int i = 2; i <= n; i++){for(int j = 0; j < i; j++){f[i] = max(f[i], max(j * (i - j), j * f[i - j]));}}return f[n];}
};

7.不同的二叉搜索树

在这里插入图片描述

思路

dp[3],就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量
元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
有2个元素的搜索树数量就是dp[2]。
有1个元素的搜索树数量就是dp[1]。
有0个元素的搜索树数量就是dp[0]。
所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]
dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]

1.f[i]: 由 1 到 i 个节点的二叉搜索树个数
2.f[i] += f[j - 1] * f[i - j]
3.f[0] = 1
4.顺序遍历

class Solution {
public:int numTrees(int n) {vector<int> f(n + 1);f[0] = 1;for(int i = 1; i <= n; i++){for(int j = 1; j <= i; j++){f[i] += f[j - 1] * f[i - j];}}return f[n];}
};

背包问题

1.01背包问题

在这里插入图片描述

思路

1.f[i][j]: 前 i 个物品在容量为 j 的情况下的最大价值
2.f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i])
3.全部 = 0
4.顺序遍历

#include<iostream>
using namespace std;
const int N = 1e3 + 10;
int f[N][N], v[N], w[N];
int n, m;int main(){scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++) scanf("%d%d", &v[i], &w[i]);for(int i = 1; i <= n; i++){for(int j = 0; j <= m; j++){// 不选f[i][j] = f[i - 1][j];// 选if(v[i] <= j) f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);}}printf("%d", f[n][m]);return 0;
}// 滚动数组优化
#include<iostream>
using namespace std;
const int N = 1e3 + 10;
int f[N], v[N], w[N];
int n, m;int main(){scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++) scanf("%d%d", &v[i], &w[i]);for(int i = 1; i <= n; i++){for(int j = m; j >= v[i]; j--){f[j] = max(f[j], f[j - v[i]] + w[i]);}}printf("%d", f[m]);return 0;
}

2.分割等和子集

在这里插入图片描述

思路

分割成两个等和子集,即找到是否存在和为 sum / 2 的子集,转化为 01 背包,背包容量为 sum / 2

1.f[j]: 背包容量为 i,放入物品后的最大重量
2.f[j] = max(f[j], f[j - nums[i]] + nums[i])
3.全部 = 0
4.倒序遍历

class Solution {
public:bool canPartition(vector<int>& nums) {int n = nums.size(), sum = 0;for(int i = 0; i < n; i++) sum += nums[i];if(sum % 2) return false;vector<int> f(10001, 0);for(int i = 0; i < n; i++){for(int j = sum / 2; j >= nums[i]; j--){f[j] = max(f[j], f[j - nums[i]] + nums[i]);if(f[j] == sum / 2) return true;}}return false;}
};

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

在这里插入图片描述

思路

尽可能分成两堆重量相同,使得相撞后重量最小

1.f[j]: 容量为 j 的背包,最大价值
2.f[j] = max(f[j], f[j - stones[i]] + stones[i])
3.全部 = 0
4.倒序遍历

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int n = stones.size(), sum = 0;for(int i = 0; i < n; i++) sum += stones[i];vector<int> f(1501, 0);for(int i = 0; i < n; i++){for(int j = sum / 2; j >= stones[i]; j--){f[j] = max(f[j], f[j - stones[i]] + stones[i]);}}return (sum - f[sum / 2]) - f[sum / 2];}
};

4.目标和

在这里插入图片描述

思路

pos - neg = tar 得 pos - (sum - pos) = tar 得 pos = (sum + tar) / 2
转换为背包容量为 pos,有多少种情况装满
无解的情况:pos 为奇数,tar 的绝对值大于 sum
只要搞到 nums[i],凑成 f[j] 就有 f[j - nums[i]] 种方法。
例如:f[j],j 为5,
已经有一个1(nums[i])的话,有 f[4]种方法 凑成 容量为5的背包。
已经有一个2(nums[i])的话,有 f[3]种方法 凑成 容量为5的背包。
已经有一个3(nums[i])的话,有 f[2]中方法 凑成 容量为5的背包
已经有一个4(nums[i])的话,有 f[1]中方法 凑成 容量为5的背包
已经有一个5(nums[i])的话,有 f[0]中方法 凑成 容量为5的背包
那么凑整 f[5] 有多少方法呢,也就是把 所有的 f[j - nums[i]] 累加起来。

1.f[j]:填满 j 背包有多少种情况
2.f[j] += f[j - nums[i]]
3.f[0] = 1,其他 = 0
4.倒序遍历

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int n = nums.size(), sum = 0;for(int i = 0; i < n; i++) sum += nums[i];if((sum + target) % 2 || abs(target) > sum) return 0;int pos = (sum + target) / 2;vector<int> f(pos + 1, 0);f[0] = 1;for(int i = 0; i < n; i++){for(int j = pos; j >= nums[i]; j--){f[j] += f[j - nums[i]];}}return f[pos];}
};

5.一和零

在这里插入图片描述

思路

可以等价为两个 01 背包,一个装 0,一个装 1

1.f[i][j]: 最多有 i 个 0 和 j 个 1 的最长子集大小
2.f[i][j] = max(f[i][j], f[i - zero][j - one] + 1)
3.全部 = 0
4.倒序遍历

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> f(m + 1, vector<int>(n + 1, 0));for(auto str : strs){int zero = 0, one = 0;for(int i = 0; i < str.size(); i++){if(str[i] == '0') zero++;else one++;  }for(int i = m; i >= zero; i--){for(int j = n; j >= one; j--){f[i][j] = max(f[i][j], f[i - zero][j - one] + 1);}}}return f[m][n];}
};

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

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

相关文章

SAP HANA中PAL算法使用入门

1 应用场合 SAP HANA作为一款内存数据库产品, 使得数据常驻内存, 物理磁盘的存储作为数据备份与日志记录, 以防断电内存中数据丢失. 这种构架大大的缩短了数据存取的时间, 使得SAP HANA很”高速”. 在传统数据模型中,数据库只是作为存取数据一个工具,对于类似下图所示的应用, 客…

5分钟速成渐变色css

色彩的分支——渐变色定义&#xff1a;按照一定规律做阶段性变化的色彩&#xff08;抽象&#xff01;&#xff01;&#xff01;&#xff09; 我们可以将图片分为两块 以中心线为参考&#xff0c;再来看渐变色的定义&#xff1a;按照一定规律做阶段性变化的色彩 既然是按一定的…

京津冀光伏展

京津冀光伏展是中国在京津冀地区举办的一项光伏产业展览活动。该展览旨在展示京津冀地区光伏产业的最新发展成果&#xff0c;促进光伏行业的交流与合作&#xff0c;推动光伏产业的可持续发展。 光伏产业是指利用太阳能将光能转化为电能的产业。作为一种清洁能源&#xff0c;光伏…

Databend 开源周报第 134 期

Databend 是一款现代云数仓。专为弹性和高效设计&#xff0c;为您的大规模分析需求保驾护航。自由且开源。即刻体验云服务&#xff1a;https://app.databend.cn 。 Whats On In Databend 探索 Databend 本周新进展&#xff0c;遇到更贴近你心意的 Databend 。 支持多语句事务…

1907_Arm Cortex-M3的基本了解

1907_Arm Cortex-M3的基本了解 全部学习汇总&#xff1a; g_arm_cores: ARM内核的学习笔记 (gitee.com) 我发现Arm Coretex-M3有一个专门的DataSheet&#xff0c;看起来这个的确是被当做了一个设计的产品来对待的。正好&#xff0c;基于这个文件来看看M3具备哪些基本的特性&…

灯塔:HTML笔记

网页由哪些部分组成&#xff1f; *文字 图片 音频 视频 超链接 程序员写的代码是通过浏览器转换成网页的 五大浏览器有哪些&#xff1f; *IE浏览器 *火狐浏览器&#xff08;Firefox&#xff09; *谷歌浏览器&#xff08;Chrome&#xff09; *Safari浏览器 *欧朋浏览器&…

【机器学习】生成对抗网络GAN

概述 生成对抗网络&#xff08;Generative Adversarial Network&#xff0c;GAN&#xff09;是一种深度学习模型架构&#xff0c;由生成器&#xff08;Generator&#xff09;和判别器&#xff08;Discriminator&#xff09;两部分组成&#xff0c;旨在通过对抗训练的方式生成逼…

【Linux】Shell命令运行原理和权限详解

【Linux】Shell命令运行原理和权限详解 一、剩余指令的补充1.tar指令2.bc指令3.uname4.热键 二、Shell命令运行原理1.Shell2.为什么Linux不让用户直接使用kernel 三、Linux权限概念四、Linux权限管理1.文件访问的用户分类2.文件类型和访问权限&#xff08;1&#xff09;文件类型…

GitHub登不上:修改hosts文件来解决(GitHub520,window)

参考链接&#xff1a;GitHub520: 本项目无需安装任何程序&#xff0c;通过修改本地 hosts 文件&#xff0c;试图解决&#xff1a; GitHub 访问速度慢的问题 GitHub 项目中的图片显示不出的问题 花 5 分钟时间&#xff0c;让你"爱"上 GitHub。 (gitee.com) GitHub网站…

Prometheus结合Grafana监控MySQL,这篇不可不读!

&#x1f4e2;&#x1f4e2;&#x1f4e2;&#x1f4e3;&#x1f4e3;&#x1f4e3; 哈喽&#xff01;大家好&#xff0c;我是【IT邦德】&#xff0c;江湖人称jeames007&#xff0c;10余年DBA及大数据工作经验 一位上进心十足的【大数据领域博主】&#xff01;&#x1f61c;&am…

IOS 发布遇到“Unable to authenticate with App Store Connect”错误咋解决?

问题&#xff1a; 在开发ios app后&#xff0c;先发布adhoc版本&#xff0c;测试通过后&#xff0c;再发布testflight版本测试&#xff0c;但是可能会遇到一下问题。 解决办法&#xff1a; 在Signing &Capabilities中&#xff0c;在ios下边要指定有发布权限的Team账号&a…

数据库之间数据迁移工具datax

简介 DataX 是阿里云 DataWorks数据集成 的开源版本&#xff0c;在阿里巴巴集团内被广泛使用的离线数据同步工具/平台。DataX 实现了包括 MySQL、Oracle、OceanBase、SqlServer、Postgre、HDFS、Hive、ADS、HBase、TableStore(OTS)、MaxCompute(ODPS)、Hologres、DRDS, databe…

链路负载均衡之DNS透明代理

一、DNS透明代理 一般来说&#xff0c;企业的客户端上都只能配置一个运营商的DNS服务器地址&#xff0c;DNS服务器通常会将域名解析成自己所在ISP内的Web服务器地址&#xff0c;这将导致内网用户的上网流量都集中在一个ISP的链路上转发&#xff0c;最终可能会造成链路拥塞&…

常用的Linux命令;Linux常用命令用法及实现方式

1.系统工作命令 (1)echo命令&#xff1a;echo命令用于在终端设备上输出字符串或变量提取后的值&#xff0c;语法格式为“echo [字符串] [$变量]”。 (2)date命令&#xff1a;date命令用于显示或设置系统的时间与日期&#xff0c;语法格式为“date [指定的格式]”。 (3)timedate…

VS2019 - error C2653: 不是类或命名空间名称

文章目录 VS2019 - error C2653: 不是类或命名空间名称概述笔记类的头文件类的实现文件备注END VS2019 - error C2653: 不是类或命名空间名称 概述 工程开了预编译头包含. 编码中, 随手写一个类, 将功能函数加入, 还没开始用这个类, 先习惯性的编译一下. 编译报错如下: St…

常用的17个运维监控系统(必备知识)

1. Zabbix Zabbix 作为企业级的网络监控工具&#xff0c;通过从服务器&#xff0c;虚拟机和网络设备收集的数据提供实时监控&#xff0c;自动发现&#xff0c;映射和可扩展等功能。 Zabbix的企业级监控软件为用户提供内置的Java应用服务器监控&#xff0c;硬件监控&#xff0c…

QT----写完的程序打包为APK在自己的手机上运行

目录 1、qt安装android组件2、打开qt配置Android 环境3、手机打开开发者模式&#xff0c;打开usb调试&#xff0c;连接电脑4、运行代码 1、qt安装android组件 qtcreater–工具-QTMaintenaceTool-startMaintenaceTool—登陆—添加或修改组件—找到android&#xff0c;安装 若是…

【脑切片图像分割】MATLAB 图像处理 源码

1. 简单图像处理 加载图像 Brain.jpg&#xff0c;使用直方图和颜色分割成区域这些区域有不同的颜色。 这是一个更高级的问题&#xff0c;有多个解决它的方法。 例如&#xff0c;您可以计算具有特定数字的图像的直方图&#xff08;例如 16 - 32&#xff09;&#xff0c;找到直方…

回归预测 | Matlab实现BiTCN基于双向时间卷积网络的数据回归预测

回归预测 | Matlab实现BiTCN基于双向时间卷积网络的数据回归预测 目录 回归预测 | Matlab实现BiTCN基于双向时间卷积网络的数据回归预测效果一览基本介绍程序设计参考资料 效果一览 基本介绍 1.Matlab实现BiTCN基于双向时间卷积网络的数据回归预测&#xff08;完整源码和数据&a…

Vue 3的Composition API和vue2的不同之处

Vue 3的Composition API是Vue.js框架的一个重要更新&#xff0c;它提供了一种新的组件逻辑组织和复用方式。在Vue 2中&#xff0c;我们通常使用Options API&#xff08;data、methods、computed等&#xff09;来组织组件的逻辑&#xff0c;但这种组织方式在处理复杂组件时可能会…