蓝桥杯练习题——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];
    }
};

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

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

相关文章

项目管理：实现高效团队协作与成功交付的关键

项目管理：实现高效团队协作与成功交付的关键

在当今竞争激烈的市场环境中&#xff0c;项目管理已成为企业成功的关键因素之一。项目管理不仅涉及时间、成本和资源的有效管理&#xff0c;还涉及到团队协作、风险管理、沟通和交付。本文将探讨项目管理的核心要素&#xff0c;以及如何实现高效团队协作和成功交付。 一、明确项…
阅读更多...
es集群的详细搭建过程

es集群的详细搭建过程

目录 一、VM配置二、集群搭建三、集群配置 一、VM配置 VM的安装 VMware Workstation 15 Pro的安装与破解 VM新建虚拟机 VM新建虚拟机 二、集群搭建 打开新建好的服务器&#xff0c;node1&#xff0c;使用xshell远程连接 下载es&#xff1a;https://www.elastic.co/cn/down…
阅读更多...
【自然语言处理六-最重要的模型-transformer-下】

【自然语言处理六-最重要的模型-transformer-下】

自然语言处理六-最重要的模型-transformer-下 transformer decoderMasked multi-head attentionencoder和decoder的连接部分-cross attentiondecoder的输出AT(Autoregresssive)NAT transformer decoder 今天接上一篇文章讲的encoder 自然语言处理六-最重要的模型-transformer-…
阅读更多...
Carbondata编译适配Spark3

Carbondata编译适配Spark3

背景 当前carbondata版本2.3.1-rc1中项目源码适配的spark版本最高为3.1,我们需要进行spark3.3版本的编译适配。 原始编译 linux系统下载源码后&#xff0c;安装maven3.6.3&#xff0c;然后执行&#xff1a; mvn -DskipTests -Pspark-3.1 clean package会遇到一些网络问题&a…
阅读更多...
SpringCloud-RabbitMQ消息模型

SpringCloud-RabbitMQ消息模型

本文深入介绍了RabbitMQ消息模型&#xff0c;涵盖了基本消息队列、工作消息队列、广播、路由和主题等五种常见消息模型。每种模型都具有独特的特点和适用场景&#xff0c;为开发者提供了灵活而强大的消息传递工具。通过这些模型&#xff0c;RabbitMQ实现了解耦、异步通信以及高…
阅读更多...
如何远程连接MySQL数据库？

如何远程连接MySQL数据库？

在现代互联网时代&#xff0c;远程连接MySQL数据库成为了许多开发者和管理员必备的技能。这不仅方便了数据的共享和管理&#xff0c;还可以使多个团队在全球范围内协同工作。本文将介绍如何通过天联组网实现远程连接MySQL数据库&#xff0c;并实现高效的信息远程通信。 天联组网…
阅读更多...
tomcat nginx 动静分离

tomcat nginx 动静分离

实验目的:当访问静态资源的时候&#xff0c;nginx自己处理 当访问动态资源的时候&#xff0c;转给tomcat处理 第一步 关闭防火墙 关闭防护 代理服务器操作&#xff1a; 用yum安装nginx tomcat &#xff08;centos 3&#xff09;下载 跟tomcat&#xff08;centos 4&#xff0…
阅读更多...
Shell管道和过滤器

Shell管道和过滤器

一、Shell管道 Shell 还有一种功能&#xff0c;就是可以将两个或者多个命令&#xff08;程序或者进程&#xff09;连接到一起&#xff0c;把一个命令的输出作为下一个命令的输入&#xff0c;以这种方式连接的两个或者多个命令就形成了管道&#xff08;pipe&#xff09;。 重定…
阅读更多...
关于 CTF 中 php 考点与绕过那些事的总结

关于 CTF 中 php 考点与绕过那些事的总结

关于 CTF 中常见 php 绕过的总结可以参考我之前的博客&#xff1a; CTF之PHP特性与绕过 PHP特性之CTF中常见的PHP绕过-CSDN博客 其中主要介绍了 md5()、sha1()、strcmp、switch、intval、$_SERVER 函数、三元运算符、strpos() 、数组、非法参数名传参等相关的绕过。 在此基础上…
阅读更多...
vue点击按钮同时下载多个文件

vue点击按钮同时下载多个文件

点击下载按钮根据需要的id调接口拿到返回需要下载的文件 再看返回的数据结构 数组中一个对象&#xff0c;就是一个文件&#xff0c;多个对象就是多个文件 下载函数 // 下载tableDownload(row) {getuploadInventoryDownload({ sysBatch: row.sysBatch, fileName: row.fileName…
阅读更多...
Linux 进程间通信

Linux 进程间通信

目录 管道 匿名管道&#xff08;pipe&#xff09; 有名管道&#xff08;fifo&#xff09; 小结 共享内存 消息队列 信号量 System V IPC的结构设计 Posix与System V的关系 管道 匿名管道&#xff08;pipe&#xff09; 我们知道&#xff0c;在Linux中通过fork创建的子…
阅读更多...
YOLOv5优化改进：下采样创新篇 | 新颖的下采样ADown | YOLOv9

YOLOv5优化改进：下采样创新篇 | 新颖的下采样ADown | YOLOv9

💡💡💡本文独家改进：新颖的下采样ADown来自于YOLOv9，助力YOLOv5，将ADown添加在backbone和head处，提供多个yaml改进方法 💡💡💡在多个私有数据集和公开数据集VisDrone2019、PASCAL VOC实现涨点 收录 YOLOv5原创自研 https://blog.csdn.net/m0_63774211/categ…
阅读更多...
MongoDB 快速入门

MongoDB 快速入门

&#x1f4d5;作者简介&#xff1a; 过去日记&#xff0c;致力于Java、GoLang,Rust等多种编程语言&#xff0c;热爱技术&#xff0c;喜欢游戏的博主。 &#x1f4d7;本文收录于MongoDB系列&#xff0c;大家有兴趣的可以看一看 &#x1f4d8;相关专栏Rust初阶教程、go语言基础…
阅读更多...
SpringMVC--03--前端传数组给后台

SpringMVC--03--前端传数组给后台

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 案例1乘客个人信息方法1&#xff1a;表单提交&#xff0c;以字段数组接收方法2&#xff1a;表单提交&#xff0c;以BeanListModel接收方法3&#xff1a;将Json对象序…
阅读更多...
电脑黑屏如何重装系统 电脑黑屏安装系统操作方法

电脑黑屏如何重装系统 电脑黑屏安装系统操作方法

据了解，75%以上的用户在使用电脑时都有碰到黑屏的现象，而电脑黑屏不但会影响自己的工作，而且还会影响自己的心情，因此，不可马虎，那么，应该怎么办呢?下面我们就来详细介绍一下 据了解，75%以上的用户在使用电脑时都有碰到黑屏的现象，而电脑黑屏不但会影响自己的工作，而…
阅读更多...
vue3三级嵌套复选框（element-plus）

vue3三级嵌套复选框（element-plus）

一、功能描述 当选择第一级的复选框时下面所有内容全选和取消全选&#xff0c;当选择第二的复选框时第三级的所有内容全选和取消全选。只要有一个第三级的内容没有选&#xff0c;二级和一级则不能勾上。第三级内容全选上了&#xff0c;第二级复选框就钩上。第二级也是同样的道理…
阅读更多...
使用GitHub API 查询开源项目信息

使用GitHub API 查询开源项目信息

一、GitHub API介绍 GitHub API 是一组 RESTful API 接口&#xff0c;用于与 GitHub 平台进行交互。通过使用 GitHub API&#xff0c;开发人员可以访问和操作 GitHub 平台上的各种资源&#xff0c;如仓库、提交记录、问题等。 GitHub API 提供了多种功能和端点&#xff0c;以…
阅读更多...
HTTP有什么缺陷，HTTPS是怎么解决的

HTTP有什么缺陷，HTTPS是怎么解决的

缺陷 HTTP是明文的&#xff0c;谁都能看得懂&#xff0c;HTTPS是加了TLS/SSL加密的&#xff0c;这样就不容易被拦截和攻击了。 SSL是TLS的前身&#xff0c;他俩都是加密安全协议。前者大部分浏览器都不支持了&#xff0c;后者现在用的多。 对称加密 通信双方握有加密解密算法…
阅读更多...
零基础如何快速入门伦敦金交易

零基础如何快速入门伦敦金交易

伦敦金交易是金融市场中备受关注的一种投资方式。对于想要学习如何炒伦敦金并快速开始交易的人来说&#xff0c;本文将为您提供一份全面而详细的指南。无论您是初学者还是有经验的交易者&#xff0c;本文都将帮助您了解伦敦金交易的基本知识&#xff0c;并提供一些实用的技巧和…
阅读更多...
如何在 Windows 11/10 中合并分区而不丢失数据

如何在 Windows 11/10 中合并分区而不丢失数据

在本文中&#xff0c;我们将了解如何在 Window 11/10 中合并分区而不丢失个人数据。每个人都会觉得需要扩大驱动器/分区的容量&#xff0c;但是在计算机中重新安装Windows对他们来说很麻烦。在 Windows PC 中合并分区的方法有很多种。我们将在下面逐步讨论一些工作方法&#xf…
阅读更多...
最新文章

Copyright @ 2022~2023