【算法——1维动态规划具体例题】

1LCR 102. 目标和

分析：分成加法和减法两个集合

#include<iostream>
#include<vector>
using namespace std;
//目标和
vector<int>nums = { 1,1,1,1,1 };
int target = 3;
int dfs(int index, int sum)  
{
	//我前面老是错就是这一步出的问题，&&intdex==nums.size否则数组不是每个数都用到
	if (sum == target && index == nums.size()) return 1;  
	if (index >= nums.size()) return 0;
	return dfs(index + 1, sum + nums[index] * -1) + dfs(index + 1, sum + nums[index]);
}


int main()
{
	cout << dfs(0, 0) << endl;


//分成加法和减法集合  各自子集都是相加
//l+r=sum  sum就是nums所有 元素和
//l-r=target    
//l=（t+sum）/2   l不能整除说明没有组合满足   
//可以整除：把l看成一个容器，然后问题就转化为nums中选容器装满l的方法数

	int sum = 0;  //计数nums总和
	for (auto i : nums)
		sum += i;
	int left = 0;
	if (abs(target) > sum || (sum + target) % 2 != 0) return 0;
	else left = (sum+target) / 2;

	vector<int>dp(left + 1);
	dp[0] = 1;
	//i循环代表选择物品范围到哪里
	for (int i = 0; i < nums.size(); i++)   //遍历物品
	{
		for (int j = left; j >= nums[i]; j--)   //遍历容量   倒序是因为每个物品只能用一次
			cout << (dp[j] += dp[j - nums[i]]) << " ";
		cout << endl;
	}


	return 0;
}

斐波那契数列：

logO(n):从底到顶

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

vector<int>memo(100,-1);
int fibonacci(int index)     //记忆化   上到下递推   O(n)
{
	if (memo[index] != -1)
		return memo[index];
	if (index == 0)
		return 0;
	if (index == 1)
		return 1;
	return memo[index] = fibonacci(index - 1) + fibonacci(index - 2);
}

int main()
{
	int n;
	cin >> n;
	cout << fibonacci(n) << endl;

	vector<int>dp(n+1,0);     //dp  下到上递推   O(logn)
	dp[1] = 1;
	for (int i = 2; i <= n; i++)
		dp[i] = dp[i - 1] + dp[i - 2];
	cout << dp[n] << endl;

	return 0;
}

983. 最低票价

#include<iostream>
#include<vector>
using namespace std;
vector<int>durations = { 1,7,30 };    //存储天数的数组
//dfs   前  to 后
int dfs(int i, vector<int>costs, vector<int>days)
{
	if (i == days.size())
		return 0;
	int ans = INT_MAX;
	for (int k = 0, j = i; k < 3; k++)
	{
		while (j < days.size() && days[i] + durations[k] > days[j])
			j++;
		ans = min(ans, dfs(j, costs, days) + costs[k]);
	}

	return ans;
}

int main()
{
	vector<int>days = { 1,2,3,4,5,6,7,8,9,10,30,31 };
	vector<int>costs = { 2,7,15 };
	cout << dfs(0, costs, days) << endl;

	//dp   后 to 前
	vector<int>dp(days.size()+1);
	int n = days.size();
	dp[n] = 0;
	for (int i = n - 1; i >= 0; i--)   //dfs就是这个for替代   i：当前指向
	{
		int ans = INT_MAX;
		for (int k = 0, j = i; k < 3; k++)    //（1,7,30）三种方案
		{
			while (j < days.size() && days[i] + durations[k] > days[j])   //当前天+（1,7,30）方案 <= days[j]    j索引就是我的后续
				j++;
			ans = min(ans, dp[j] + costs[k]);   //三个方案花费选最小
		}
		dp[i] = ans;
	}

	for (auto i : dp)
		cout << i << " ";

	return 0;
}

91. 解码方法

这道题的理解：

注意这个return 1和dp[n]=1；

我们先说dfs，以123为例子，从1-3不停递归，直到越界，我们就知道匹配成功，返回1，然后开始匹配2个，又直到越界，利用这个”1“一直往前推。

然后dp就是dfs的傀儡，因为越界就成功，返回1；

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

int dfs(string s,int i)
{
	//说明匹配成功
	if (i >= s.size()) return 1;
	int ans = 0;
	if (s[i] == '0')  //之前匹配模式有问题
		ans = 0;
	else
	{
		//s[i]!=0
		ans = dfs(s, i + 1);   //i字符匹配
		if (i + 1 < s.size() && (s[i] - '0') * 10 + s[i + 1] - '0' <= 26)   //符合结合条件
			ans += dfs(s, i + 2);    //i和i+1一起匹配；然后跳到i+2开始。
	} 
	return ans;
}

int main()
{
	string str("1123");
	cout << "dfs:" << dfs(str, 0) << endl << endl;

	int n = str.size();
	vector<int>dp(n + 1);    //这个dp含义：把当前这个算上，以及后面的字符；一共有多少种拼法
	dp[n] = 1;
	for (int i = n - 1; i >= 0; i--)
	{
		int ans;
		if (str[i] == '0')
			ans = 0;
		else
		{
			ans= dp[i + 1];   //只选当前的
			if (i + 1 < n && (str[i] - '0') * 10 + str[i] - '0' <= 26)
				ans+= dp[i + 2];    //选当前和其下一个
		}
		dp[i] = ans;
	}

	cout << "dp:";
	for (auto i : dp)
		cout << i << " ";

	return 0;
}

解码方法2：

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

long mod = 1000000007;    //答案和 10^9+7取余

long dfs(int index, string str)
{
	long ans = 0;
	if (index == str.size())
		return 1;
	if (str[index] == '0')
		return 0;
	else
	{
		if (str[index] != '*')
		{
			ans = dfs(index + 1, str);
			if (index + 1 < str.size() && str[index + 1] != '*')
			{
				if (index + 1 < str.size() && (str[index] - '0') * 10 + str[index + 1] - '0' <= 26)
				{
					ans += dfs(index + 2, str);
				}
			}
			else if (index + 1 < str.size() && str[index + 1] == '*')
			{
				if (str[index] == '1') ans += dfs(index + 2, str) * 9;
				else if (str[index] == '2') ans += dfs(index + 2, str) * 6;
			}

		}
		else if (str[index] == '*')
		{
			ans = 9 * dfs(index + 1, str);
			if (index + 1 < str.size())
			{
				if (str[index + 1] == '*')
				{
					ans += dfs(index + 2, str) * 15;
				}
				else if (str[index + 1] != '*')
				{
					if (str[index + 1] <= '6') ans += dfs(index+2,str) * 2;
					else ans += dfs(index + 2, str) * 1;
				}
			}
		}

	}

	return ans%mod;
}

int main()
{
	string str = "7*9*3*6*3*0*5*4*9*7*3*7*1*8*3*2*0*0*6*";
	cout << dfs(0, str) << endl << endl;

	int n = str.size();
	vector<long long>dp(n + 1);
	dp[n] = 1;
	for (int index = n - 1; index >= 0; index--)
	{
		if (str[index] != '0')
		{
			if (str[index] != '*')
			{
				dp[index] = dp[index + 1];
				if (index + 1 < str.size() && str[index + 1] != '*')
				{
					if (index + 1 < str.size() && (str[index] - '0') * 10 + str[index + 1] - '0' <= 26)
					{
						dp[index] += dp[index + 2];
					}
				}
				else if (index + 1 < str.size() && str[index + 1] == '*')
				{
					if (str[index] == '1') dp[index] += dp[index + 2] * 9;
					else if (str[index] == '2') dp[index] += dp[index + 2] * 6;
				}

			}
			else if (str[index] == '*')
			{
				dp[index] = 9 * dp[index + 1];
				if (index + 1 < str.size())
				{
					if (str[index + 1] == '*')
					{
						dp[index] += dp[index + 2] * 15;
					}
					else if (str[index + 1] != '*')
					{
						if (str[index + 1] <= '6') dp[index] += dp[index + 2] * 2;
						else dp[index] += dp[index + 2] * 1;
					}
				}
			}

		}
		dp[index] %= mod;
	}

	for (auto i : dp)
		cout << (int)i << " ";

	return 0;
}

力扣字符串环绕

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<stack>
#include<string>
#include<map>
using namespace std;

void dp1(string str)    //我的写法错误
{

	map<char, int>ma;
	for (int i = 0; i < str.size(); i++)
	{
		if (str[i] == 'a' && i > 0 && str[i - 1] == 'z')
		{
			ma['a'] = ma['z'] + 1;
		}
		else if (i > 0 && str[i - 1] == str[i] - 1)
		{

			ma[str[i]] = ma[str[i - 1]] + 1;
		}
		else
			ma[str[i]] = max(ma[str[i]], 1);
	}

	int ans = 0;
	for (auto i : ma)
	{
		ans += i.second;
		cout << i.first << "-" << i.second << "    ";
	}
	cout << endl;
	cout << ans << endl << endl << endl;

}

void dp2(string str)    //纠正
{
	map<char, int>ma;
	int len = 0;
	for (int i = 0; i < str.size(); i++)
	{
		if (i > 0 && (str[i] == 'a' && str[i - 1] == 'z' || str[i - 1] == str[i] - 1))
		{
			len++;
		}
		else
			len = 1;
		ma[str[i]] = max(ma[str[i]], len);
	}

	int ans = 0;
	for (auto i : ma)
	{
		ans += i.second;
		cout << i.first << "-" << i.second << "    ";
	}
	cout << endl;
	cout << ans << endl << endl << endl;

}


int main()
{
	string str("abcdefghijklmnopqrstuvwxymnopqrstuvwxyz");

	cout << str << endl << endl;
	dp1(str);
	dp2(str);

	return 0;
}

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

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

相关文章

【成长day】NeRF学习记录1：预备知识nerf论文算法学习

【成长day】NeRF学习记录1：预备知识nerf论文算法学习

个人知乎文章链接&#xff1a;https://zhuanlan.zhihu.com/p/3383996241 预备知识 NeRF重建 NeRF的全称是Neural Radiance Fields&#xff0c;即将场景表示为视场合成的神经辐射场&#xff0c;用神经网络来拟合辐射场&#xff0c;实现对三维场景的隐式表示。本质是完成了图形…
阅读更多...
[项目详解][boost搜索引擎#2] 建立index | 安装分词工具cppjieba | 实现倒排索引

[项目详解][boost搜索引擎#2] 建立index | 安装分词工具cppjieba | 实现倒排索引

目录 编写建立索引的模块 Index 1. 设计节点 2.基本结构 3.(难点) 构建索引 1. 构建正排索引&#xff08;BuildForwardIndex&#xff09; 2.❗构建倒排索引 3.1 cppjieba分词工具的安装和使用 3.2 引入cppjieba到项目中 倒排索引代码 本篇文章&#xff0c;我们将继续项…
阅读更多...
Android——事件冲突处理

Android——事件冲突处理

当我们给列表的item设置了点击事件后&#xff0c;又给item中的按钮设置了点击事件&#xff0c;此时item的点击事件会失效。 解决 给item的布局xml中设置以下属性 android:descendantFocusability"blocksDescendants"<LinearLayout xmlns:android"http://sc…
阅读更多...
005：航空力学基础、无人机操纵、飞机性能

005：航空力学基础、无人机操纵、飞机性能

摘要&#xff1a;本文详细介绍无人机稳定性、操控性、飞机性能等概念。 一、飞机的稳定性 概念&#xff1a; 飞机的稳定性&#xff08;安定性&#xff09;&#xff0c;是指在飞机受到扰动后&#xff0c;不经飞行员操纵&#xff0c;能恢复到受扰动前的原始状态&#xff08;即原…
阅读更多...
Android系统架构

Android系统架构

Android系统架构&#xff1a; Android系统架构是一个复杂的、分层的结构&#xff0c;旨在提供高度的灵活性和可扩展性。这个架构可以大致分为以下几个主要层次&#xff1a; Linux Kernel&#xff08;Linux内核&#xff09;&#xff1a; Linux内核是Android系统的底层&#xff0…
阅读更多...
OAK相机的RGB-D彩色相机去畸变做对齐

OAK相机的RGB-D彩色相机去畸变做对齐

▌低畸变标准镜头的OAK相机RGB-D对齐的方法 OAK相机内置的RGB-D管道会自动将深度图和RGB图对齐。其思想是将深度图像中的每个像素与彩色图像中对应的相应像素对齐。产生的RGB-D图像可以用于OAK内置的图像识别模型将识别到的2D物体自动映射到三维空间中去&#xff0c;或者产生的…
阅读更多...
OpenSSL

OpenSSL

OpenSSL 概述 OpenSSL 是一个开源的、安全传输协议实现工具&#xff0c;广泛应用于数据加密与解密、证书生成与管理以及其他安全性相关的任务。在现代网络安全中&#xff0c;OpenSSL 被用于构建和维护 SSL/TLS 通信&#xff0c;确保数据在传输过程中的机密性和完整性。 简单来…
阅读更多...
西圣和绿联电容笔哪款好用？西圣、绿联和uhb电容笔真实避坑测评!

西圣和绿联电容笔哪款好用？西圣、绿联和uhb电容笔真实避坑测评!

现在市面上的平替电容笔种类非常多&#xff0c;在购买的时候大多数人都没有非常确定的目标&#xff0c;这主要是因为大多数人对电容笔的认识程度不够。 作为一个有着多年数码产品测评经验的测评员&#xff0c;我刚好对电容笔也有比较深刻的理解&#xff0c;也借着大家问我关于…
阅读更多...
ASP.NET MVC-font awesome-localhost可用IIS不可用

ASP.NET MVC-font awesome-localhost可用IIS不可用

环境&#xff1a; win10, .NET 6.0&#xff0c;IIS 问题描述 本地IIS正常显示&#xff0c;但放到远程服务器上&#xff0c;每个icon都显示?。同时浏览器的控制台报错&#xff1a; fontawesome-webfont.woff2:1 Failed to load resource: the server responded with a statu…
阅读更多...
【网络协议栈】Tcp协议（上）结构的解析 和 Tcp中的滑动窗口（32位确认序号、32位序号、4位首部长度、6位标记位、16为窗口大小、16位紧急指针）

【网络协议栈】Tcp协议（上）结构的解析 和 Tcp中的滑动窗口（32位确认序号、32位序号、4位首部长度、6位标记位、16为窗口大小、16位紧急指针）

绪论​ “没有那么多天赋异禀&#xff0c;优秀的人总是努力翻山越岭。”本章主要讲到了再五层网络协议从上到下的第二层传输层中使用非常广泛的Tcp协议他的协议字段结构&#xff0c;通过这些字段去认识其Tcp协议运行的原理底层逻辑和基础。后面将会再写一篇Tcp到底是通过什么调…
阅读更多...
java实现的音视频格式转化器

java实现的音视频格式转化器

一、前言 最近写了一款图形界面版的音视频格式转化器&#xff0c;可以实现将多种视频之间进行转化&#xff0c;非常好用&#xff0c;如将AVI转换为&#xff0c;TS&#xff0c;FLV&#xff0c;MP4等。音频可将MP3转成WAV。 二、实现 1.需引入相关maven依赖。 <!-- 核心包 -…
阅读更多...
群控系统服务端开发模式-应用开发-业务架构逻辑开发准备工作

群控系统服务端开发模式-应用开发-业务架构逻辑开发准备工作

安装与仓库已经调整完毕&#xff0c;现在开发业务架构逻辑&#xff0c;其次再开发功能逻辑。业务架构逻辑开发与功能逻辑开发不是一回事&#xff0c;一定要明白。业务架构指的是做某一件事或是某一种类型的事的逻辑&#xff0c;在互联网web应用中通常指一套系统的外在逻辑&…
阅读更多...
知识见闻 - 磁力片原理

知识见闻 - 磁力片原理

磁力片是一种利用磁性原理设计的玩具&#xff0c;它的工作原理和磁性方向的排列方式非常有趣。让我们深入了解一下磁力片的核心原理和磁性方向的特点。 磁力片的基本原理 磁力片的工作原理基于磁铁的基本特性。每个磁力片都包含多个小磁铁&#xff0c;这些磁铁被精心排列&#…
阅读更多...
强化学习数学原理学习(一)

强化学习数学原理学习(一)

前言 总之开始学! 正文 先从一些concept开始吧,有一个脉络比较好 state 首先是就是状态和状态空间,显而易见,不多说了 action 同理,动作和动作空间 state transition 状态转换,不多说 policy 策略,不多说 reward 奖励,不多说 MDP(马尔科夫) 这里需要注意到就是这个是无…
阅读更多...
小程序视频SDK解决方案，提供个性化开发和特效定制设计

小程序视频SDK解决方案，提供个性化开发和特效定制设计

美摄科技作为视频处理技术的领航者&#xff0c;深知在这一变革中&#xff0c;每一个细微的创新都能激发无限可能。因此&#xff0c;我们精心打造了一套小程序视频SDK解决方案&#xff0c;旨在满足不同行业、不同规模客户的多元化需求&#xff0c;携手共创视频内容的璀璨未来。 …
阅读更多...
守护头顶安全——AI高空抛物监测，让悲剧不再重演

守护头顶安全——AI高空抛物监测，让悲剧不再重演

在城市的喧嚣中&#xff0c;我们享受着高楼林立带来的便捷与繁华&#xff0c;却往往忽视了那些隐藏在高空中的危险。近日&#xff0c;震惊全国的高空抛物死刑案件被最高院核准并执行。案件中被告人多次高空抛物的举动&#xff0c;夺去了无辜者的生命&#xff0c;也让自己付出了…
阅读更多...
Leetcode11:盛水最多的容器

Leetcode11:盛水最多的容器

原题地址&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 题目描述&#xff1a; 给定一个长度为 n 的整数数组 height 。有 n 条垂线&#xff0c;第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线&#xff0c;使得它们与 x 轴共同构成的容器可以容纳…
阅读更多...
Docker本地安装Minio对象存储

Docker本地安装Minio对象存储

Docker本地安装Minio对象存储 1. 什么是 MinIO&#xff1f; MinIO 是一个开源的对象存储服务器。这意味着它允许你在互联网上存储大量数据&#xff0c;比如文件、图片、视频等&#xff0c;而不需要依赖传统的文件系统。MinIO 的特点在于它非常灵活、易于使用&#xff0c;同时…
阅读更多...
Pr 视频效果：波形变形

Pr 视频效果：波形变形

视频效果/扭曲/波形变形 Distort/Wave Warp 波形变形 Wave Warp效果用于在剪辑上创建类似波浪的动态变形效果。 此效果会自动动画化&#xff0c;波形以恒定速度移动。要改变速度或停止波动&#xff0c;需要设置关键帧。 ◆ ◆ ◆ 效果选项说明 通过调整波形的类型、高度、宽度…
阅读更多...
（六）问题记录，simulink仿真出现模型碰撞后穿越

（六）问题记录，simulink仿真出现模型碰撞后穿越

明明已经设置了车轮和地面之间的 spatial contact force&#xff0c;可是还会出现模型穿越&#xff08;重力作用下自由落体&#xff09;&#xff0c;如下图所示。 可仅降低小车初始高度后就不会穿越&#xff0c;如下图所示。 初步怀疑是小车初始高度大的话&#xff0c;小车在和…
阅读更多...
最新文章

Copyright @ 2022~2023