动态规划dp_4

一.背包

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

二.题

1.

思路：dp五部曲，思路在注释


/*
dp[i]表示：到达第 i 个台阶有dp[i]种方法
状态转移方程：dp[i] = dp[i-1] + dp [i-2] + dp[i-3] +  .... + dp[i-m]; 
既有：dp[i] +=dp[i-j];
初始化：从1到m都初始化为1
遍历方向，从下往上遍历
*/

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int n,m;
    cin>>n>>m;
    
    vector<int>dp(n+1);
    for(int i = 1; i <= m; i++)dp[i] = 1;
    
    for(int i = 2; i <= n; i++){
        for(int j = 1;j <= m && j < i; j++){
            dp[i] += dp[i-j];
        }
    }
    cout<<dp[n];
    return 0;
}

 2.

思路：dp五部曲，思路在注释

/*
dp[i]：表示当钱为 i 时，最小的组成方式为dp[i]
状态转移方程：遍历钱有dp[i] = min(dp[i],dp[i-j]+1)
初始化：dp[0] = 1;
遍历顺序：先背包，后钱
*/

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int>dp(amount+1,INT_MAX);
        dp[0] = 0;

        for(int i = 1; i <= amount; i++){
            for(int j = coins.size()-1; j>=0; j--){
                int coin = coins[j];
                if(i>=coin&&dp[i-coin]!=INT_MAX)
                    dp[i] = min(dp[i],dp[i-coin]+1);
            }
        }
        if(dp[amount]==INT_MAX)return -1;
        else return dp[amount];
    }
};

3. 

思路：五部曲，注释

/*
dp[i]:当数为 i 时，完全平方数之和最小数量为dp[i]
状态转移方程：dp[i] = min(dp[i],dp[i-j*j]+1)
初始化：dp[0] = 0;
遍历顺序：都行
*/

class Solution {
public:
    int numSquares(int n) {

        vector<int>dp(n+1,INT_MAX);
        dp[0] = 0;

        for(int i = 1; i <= n;i++){
            for(int j = 1; j * j<= i; j++){
                dp[i] = min(dp[i],dp[i - j * j]+1);
            }
        }
        return dp[n];

    }
};

 4.这个题得收藏

 

思路： 

  1. 确定dp数组以及下标的含义

dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。

  1. 确定递推公式

如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。

所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。

  1. dp数组如何初始化

从递推公式中可以看出，dp[i] 的状态依靠 dp[j]是否为true，那么dp[0]就是递推的根基，dp[0]一定要为true，否则递推下去后面都都是false了。

那么dp[0]有没有意义呢？

dp[0]表示如果字符串为空的话，说明出现在字典里。

但题目中说了“给定一个非空字符串 s” 所以测试数据中不会出现i为0的情况，那么dp[0]初始为true完全就是为了推导公式。

下标非0的dp[i]初始化为false，只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。

  1. 确定遍历顺序

题目中说是拆分为一个或多个在字典中出现的单词，所以这是完全背包。

还要讨论两层for循环的前后顺序。

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。


class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        for (int i = 1; i <= s.size(); i++) {   // 遍历背包
            for (int j = 0; j < i; j++) {       // 遍历物品
                string word = s.substr(j, i - j); //substr(起始位置，截取的个数)
                if (wordSet.find(word) != wordSet.end() && dp[j]) {
                    dp[i] = true;
                }
            }
        }
        return dp[s.size()];
    }
};

5.多重背包

思路：01背包的变种题型，只需要多加一层for循坏来控制住次数即可

#include <iostream>
#include <vector>
using namespace std;

int C,N;

int main(){
    cin>>C>>N;
    vector<int>dp(C+1,0);// dp数组
    
    vector<int>weight(N+1);
    vector<int>value(N+1);
    vector<int>nums(N+1);
    
    for(int i = 1;i <= N;i++) cin>>weight[i];
    for(int i = 1;i <= N;i++) cin>>value[i];
    for(int i = 1;i <= N;i++) cin>>nums[i];
    
    for(int i = 0; i <= N; i++){  // 物品
        for(int j = C; j >= weight[i]; j--){  //背包
            
            for(int k = 1; k <= nums[i] && (j - k * weight[i])>=0; k++){
                dp[j] = max(dp[j],dp[j - k * weight[i]] + k * value[i]);
            }
            
        }
    }
    cout<<dp[C];
    return 0;
}

6.

思路：dp五部曲，思路在注释

/*
dp[i]:数组的含义为从 1 到 i 家 可偷取的最大金额为 dp[i]
状态转移方程：对于 i 号房子时 有 偷与不偷 俩个状态
偷 i 时 有 dp[i-2] + val[i]
不偷 i 时 有 dp[i-1]
既有 dp[i] = max(dp[i-1],dp[i-2]+val[i]);
初始化：对于 1 和 2房间来说，1是必偷的房间，而对于 2考虑max(val[1],val[2])
遍历顺序：从前往后
*/
class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size()==1)return nums[0];
        else if(nums.size()==2)return max(nums[0],nums[1]);
        vector<int>dp(nums.size());
         
        dp[0] = nums[0];
        dp[1] = max(nums[0],nums[1]);

        for(int i = 2;i < nums.size(); i++){
            dp[i] = max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[nums.size()-1];
    }
};

 7.

思路：dp五部曲，思路在注释

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 1) return nums[0]; 
        if (nums.size() == 2) return max(nums[0], nums[1]); 


        vector<int> dp1(nums.size());
        dp1[0] = nums[0];
        dp1[1] = max(nums[0], nums[1]);
        for (int i = 2; i < nums.size() - 1; i++) {
            dp1[i] = max(dp1[i - 1], dp1[i - 2] + nums[i]);
        }


        vector<int> dp2(nums.size());
        dp2[0] = 0;
        dp2[1] = nums[1];
        for (int i = 2; i < nums.size(); i++) {
            dp2[i] = max(dp2[i - 1], dp2[i - 2] + nums[i]);
        }

        return max(dp1[nums.size() - 2], dp2[nums.size() - 1]);
    }
};

 8.

思路：注释

class Solution {
public:
    int rob(TreeNode* root) {
        vector<int> result = robTree(root);
        return max(result[0], result[1]);
    }
    // 长度为2的数组，0：不偷，1：偷
    vector<int> robTree(TreeNode* cur) {
        if (cur == NULL) return vector<int>{0, 0};
        vector<int> left = robTree(cur->left);
        vector<int> right = robTree(cur->right);
        // 偷cur，那么就不能偷左右节点。
        int val1 = cur->val + left[0] + right[0];
        // 不偷cur，那么可以偷也可以不偷左右节点，则取较大的情况
        int val2 = max(left[0], left[1]) + max(right[0], right[1]);
        return {val2, val1};
    }
};

9.

思路：贪心和动态规划

贪心

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int cost = INT_MAX, profit = 0;
        for (int price : prices) {
            cost = min(cost, price);
            profit = max(profit, price - cost);
        }
        return profit;
    }
};

 dp

/*
买入的价格是随着遍历更新最小值的
dp则是买入后更新的获利最大值

dp[i] : 表示当第 i 天卖出的最大值
状态转移方程：dp[i] = max(dp[i-1],prices[i] - min_in)
初始化：dp[0] = 0;
遍历顺序：前到后

*/

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (n == 0) return 0;

        int minprice = prices[0];
        vector<int> dp (prices.size(), 0);

        for (int i = 1; i < prices.size(); i++){
            minprice = min(minprice, prices[i]);
            dp[i] = max(dp[i - 1], prices[i] - minprice);
        }
        return dp[n - 1];
    }
};

10.

思路：五部曲，思路在注释

/*
dp含义
dp[i][0]: 表示为从第 1 天到 i 天持有股票时利润最大值为dp[i][0]
dp[i][1]: 表示为从第 1 天到 i 天不持有股票利润最大值为dp[i][1]
状态转移方程：
dp[i][0] = max(dp[i - 1][0],dp[i - 1][1] + prices[i]); // 手不持股票
dp[i][1] = max(dp[i - 1][1],dp[i - 1][0] - prices[i]); // 手持股票
初始化：
dp[0][0] = 0
dp[0][1] = -prices[0];
遍历顺序：
关系由递推得到，所以从头到尾
*/
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>>dp(prices.size(),vector<int>(2));
        dp[0][0] = 0;dp[0][1] = -prices[0];

        for(int i = 1;i < prices.size(); i++){
            dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1] = max(dp[i-1][1],dp[i-1][0]-prices[i]);
        }
        return dp[prices.size()-1][0];
    }
};

 11.算法竞赛进阶指南

思路:诶呦，我的妈呀 ，这是什么题？

找规律，先看小的n = 1，n = 2，n = 3的情况，然后调用递归函数

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>
using namespace std;
char mp[730][730];
void f(int n, int x, int y) {
	if (n == 1)mp[x][y] = 'X';
	else {
		int m = pow(3, n - 2);
		f(n - 1, x, y);
		f(n - 1, x + 2 * m, y);
		f(n - 1, x, y + 2 * m);
		f(n - 1, x + m, y + m);
		f(n - 1, x + 2 * m, y + 2 * m);
	}
}
int main() {
	int n;
	while (1) {
		cin >> n;
		if (n == -1) return 0;
		int c = pow(3, n - 1);
		memset(mp, ' ', sizeof(mp));
		f(n, 0, 0);
		for (int i = 0; i < c; i++) {
			for (int j = 0; j < c; j++) cout << mp[i][j];
			cout << endl;
		}
		cout << '-' << endl;
	}
	return 0;
}

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

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

相关文章

SpringBoot整合easy-es

SpringBoot整合easy-es

一、easy-es简介 EasyES是一款基于Elasticsearch官方提供的RestHighLevelClient开发的ORM框架&#xff0c;旨在简化开发流程并提高效率。 EasyES在保持RestHighLevelClient原有功能的基础上进行增强&#xff0c;而不做任何改变。它采用与Mybatis-Plus相似的语法&#xff0c;使得…
阅读更多...
B样条曲线插值边界条件

B样条曲线插值边界条件

以下内容来自deepseek&#xff0c;准确性未知&#xff0c;若有疑问&#xff0c;欢迎交流讨论。 1. 切矢条件&#xff08;Tangent Vector Condition&#xff09; 定义&#xff1a;在曲线的起点或终点处指定一阶导数&#xff08;切线方向&#xff09;&#xff0c;强制曲线在端点…
阅读更多...
java集合框架之Map系列

java集合框架之Map系列

前言 首先从最常用的HashMap开始。HashMap是基于哈希表实现的&#xff0c;使用数组和链表&#xff08;或红黑树&#xff09;的结构。在Java 8之后&#xff0c;当链表长度超过阈值时会转换为红黑树&#xff0c;以提高查询效率。哈希冲突通过链地址法解决。需要明确的是&#xff…
阅读更多...
系统思考—慢就是快

系统思考—慢就是快

“所有成长&#xff0c;都是一个缓慢渗透的过程&#xff0c;回头看&#xff0c;才发现自己已经走了很远。” —— 余秋雨 这让我想起一个最近做的项目。和一家公司合作&#xff0c;他们的管理模式一直陷入困境&#xff0c;员工积极性低&#xff0c;领导层的决策效率也不高。刚…
阅读更多...
体验 DeepSeek-R1：解密 1.5B、7B、8B 版本的强大性能与应用

体验 DeepSeek-R1：解密 1.5B、7B、8B 版本的强大性能与应用

文章目录 &#x1f34b;引言&#x1f34b;DeepSeek 模型简介&#x1f34b;版本更新&#xff1a;1.5B、7B、8B 的区别与特点&#x1f34b;模型评估&#x1f34b;体验 DeepSeek 的过程&#x1f34b;总结 &#x1f34b;引言 随着大规模语言模型的持续发展&#xff0c;许多模型在性…
阅读更多...
前缀和、区间和的差别

前缀和、区间和的差别

【前缀和】 定义&#xff1a;前缀和是指一个数组&#xff08;或矩阵&#xff09;中&#xff0c;从第一个元素到当前元素的累加和。通过预处理数组&#xff0c;构造一个前缀和数组&#xff0c;使得前缀和数组的每个元素表示原数组从第一个元素到该元素的累加和。‌ 用途&#xf…
阅读更多...
数据开放共享和平台整合优化取得实质性突破的智慧物流开源了

数据开放共享和平台整合优化取得实质性突破的智慧物流开源了

智慧物流视频监控平台是一款功能强大且简单易用的实时算法视频监控系统。它的愿景是最底层打通各大芯片厂商相互间的壁垒&#xff0c;省去繁琐重复的适配流程&#xff0c;实现芯片、算法、应用的全流程组合&#xff0c;从而大大减少企业级应用约95%的开发成本可通过边缘计算技术…
阅读更多...
K8s组件

K8s组件

一、Kubernetes 集群架构组件 K8S 是属于主从设备模型&#xff08;Master-Slave 架构&#xff09;&#xff0c;即有 Master 节点负责集群的调度、管理和运维&#xff0c;Slave 节点是集群中的运算工作负载节点。 主节点一般被称为 Master 节点&#xff0c;master节点上有 apis…
阅读更多...
使用 Vite + React 19 集成 Tailwind CSS 与 shadcn/ui 组件库完整指南

使用 Vite + React 19 集成 Tailwind CSS 与 shadcn/ui 组件库完整指南

使用 Vite React 19 集成 Tailwind CSS 与 shadcn/ui 组件库完整指南 &#x1f31f; 前言一、创建 React 19 项目二、集成 Tailwind CSS1️⃣ 安装依赖2️⃣ 配置 Vite 插件3️⃣ 引入 Tailwind4️⃣ 启动项目 三、配置路径别名1️⃣ 修改 TypeScript 配置2️⃣ 安装类型声明3…
阅读更多...
基于Go语言 XTA AI聊天界面实现

基于Go语言 XTA AI聊天界面实现

项目开源地址: XTA-AI-SDK 人工智能技术的迅速发展&#xff0c;AI聊天应用变得越来越流行。本文将介绍如何使用Go语言和LCL库&#xff08; Lazarus Component Library&#xff09;创建一个功能丰富的AI聊天界面。项目主要包含以下模块&#xff1a; 项目背景 本项目旨在为开发…
阅读更多...
Spring安装和使用(Eclipse环境)

Spring安装和使用(Eclipse环境)

一、Spring框架概述 1、 什么是Spring Spring是一个开源框架&#xff0c;Spring是于2003 年兴起的一个轻量级的Java 开发框架&#xff0c;由Rod Johnson 在其著作Expert One-On-One J2EE Development and Design中阐述的部分理念和原型衍生而来。它是为了解决企业应用开发的复…
阅读更多...
石子合并

石子合并

断环为链。 环形的最优合并方式&#xff0c;一定可以展开成长为n的链来处理。 怎样才是最优的合并方式&#xff1f; n<100。 枚举处理。 #include<bits/stdc.h> using namespace std;signed main() {int n; cin>>n;vector<int>a(nnn1),suma;for(int …
阅读更多...
在nodejs中使用RabbitMQ（六）sharding消息分片

在nodejs中使用RabbitMQ（六）sharding消息分片

RabbitMQ 的分片插件&#xff08;rabbitmq_sharding&#xff09;允许将消息分布到多个队列中&#xff0c;这在消息量很大或处理速度要求高的情况下非常有用。分片功能通过将消息拆分到多个队列中来平衡负载&#xff0c;从而提升消息处理的吞吐量和可靠性。它能够在多个队列之间…
阅读更多...
半遮挡检测算法 Detecting Binocular Half-Occlusions

半遮挡检测算法 Detecting Binocular Half-Occlusions

【1. 背景】&#xff1a; 本文分析【Detecting Binocular Half-Occlusions&#xff1a;Empirical Comparisons of Five Approaches】Geoffrey Egnal和Richard P. Wildes于2002年发表在IEEE Transactions on Pattern Analysis and Machine Intelligence上&#xff0c;这是1篇中…
阅读更多...
《open3d +pyqt》AABB计算

《open3d +pyqt》AABB计算

《open3d +pyqt》AABB计算 一、效果展示二、qt设置2.1界面设置2.2 py文件生成三、核心代码一、效果展示 二、qt设置 2.1界面设置 添加动作AABB： 布局参数： 2.2 py文件生成 更新Mainwindow.py 生成py文件 三、核心代码 代码如下： main.py文件
阅读更多...
CAS单点登录（第7版）10.多因素身份验证

CAS单点登录（第7版）10.多因素身份验证

如有疑问&#xff0c;请看视频&#xff1a;CAS单点登录&#xff08;第7版&#xff09; 多因素身份验证 概述 多因素身份验证 &#xff08;MFA&#xff09; 多因素身份验证&#xff08;Multifactor Authentication MFA&#xff09;是一种安全机制&#xff0c;要求用户提供两种…
阅读更多...
LeetCode1706

LeetCode1706

LeetCode1706 目录 LeetCode1706题目描述示例题目理解问题描述 示例分析思路分析问题核心 代码段代码逐行讲解1. 获取网格的列数2. 初始化结果数组3. 遍历每个球4. 逐行模拟下落过程5. 检查是否卡住6. 记录结果7. 返回结果数组 复杂度分析时间复杂度空间复杂度 总结的知识点1. …
阅读更多...
坐井说天阔---DeepSeek-R1

坐井说天阔---DeepSeek-R1

前言 DeepSeek-R1这么火&#xff0c;虽然网上很多介绍和解读&#xff0c;但听人家的总不如自己去看看原论文。于是花了大概一周的时间&#xff0c;下班后有进入了研究生的状态---读论文。 DeepSeek这次的目标是探索在没有任何监督数据的情况下训练具有推理能力的大模型&#…
阅读更多...
moveable 一个可实现前端海报编辑器的 js 库

moveable 一个可实现前端海报编辑器的 js 库

目录 缘由-胡扯本文实验环境通用流程1.基础移动1.1 基础代码1.1.1 data-* 解释 1.2 操作元素创建1.3 css 修饰1.4 cdn 引入1.5 js 实现元素可移动1.6 图片拖拽2.缩放3.旋转4.裁剪 懒得改文案了&#xff0c;海报编辑器换方案了&#xff0c;如果后面用别的再更。 缘由-胡扯 导火…
阅读更多...
滑动窗口算法篇：连续子区间与子串问题

滑动窗口算法篇：连续子区间与子串问题

1.滑动窗口原理 那么一谈到子区间的问题&#xff0c;我们可能会想到我们可以用我们的前缀和来应用子区间问题&#xff0c;但是这里对于子区间乃至子串问题&#xff0c;我们也可以尝试往滑动窗口的思路方向去进行一个尝试&#xff0c;那么说那么半天&#xff0c;滑动窗口是什么…
阅读更多...
最新文章

Copyright @ 2022~2023