蓝桥杯:最优包含--动态规划(C语言)

这篇具有很好参考价值的文章主要介绍了蓝桥杯:最优包含--动态规划(C语言)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

最优包含c语言,编程题,蓝桥杯,动态规划,c语言
最优包含c语言,编程题,蓝桥杯,动态规划,c语言

思路(动态规划)

1、S串用i进行遍历,T串用j进行遍历。

2、dp数组[i][j]的含义:S串中从S[0]到S[i],最少修改dp[i][j]个字符,可以包含T串中从T[0]到T[j]这部分字符串。

3、遍历时遇到的情况有两种:

(1)情况一:S[i]==T[j]
       dp[i][j]=min(dp[i-1][j],dp[i-1][j-1]);
       dp[i-1][j]的含义:S[0]到S[i-1]中最少修改dp[i-1][j]个字符包含T[0]到T[j]。
       dp[i-1][j-1]的含义:S[0]到S[i-1]中最少修改dp[i-1][j-1]个字符串包含T[0]到T[j-1]。

情况二:S[i]!=T[j]
       dp[i][j]=min(dp[i-1][j-1]+1,dp[i-1][j]);
       dp[i-1][j-1]+1的含义:dp[i-1][j-1]的含义是S[0]到S[i-1]中最少修改dp[i-1][j-1]个字符,使其包含T[0]到T[j-1],那么+1说明S[i]!=T[j],需要修改最后一个字符。
       dp[i-1][j]的含义:S[0]到S[i-1]中最少修改dp[i-1][j]个字符,使其包含T[0]到T[j],其表达的意思是S[0]到S[i-1]中,包含T[0]到T[j]的最小次数。

4、dp数组初始化问题
(1)因为要求的是最小值,所以dp数组初始化应为最大值,就像我们在求“最大”的动态规划时,初始化为最小值一样。
(2)j==0的时候说明T为空串,所以S串一个字符也不用修改,所以dp[i][0]=0。文章来源地址https://www.toymoban.com/news/detail-598300.html

代码

#include<stdio.h>
#include<string.h>
#include<limits.h>//用于获取最大值INT_MAX,INT_MIN(最小值) 
char S[1000];
char T[1000];
int dp[1001][1001];

//返回两数的最小值函数 
int min(int x,int y){
	
	if(x<y){
		return x;
	}else{
		return y;
	}
	
}

int main(){
	//输入字符串S 
	gets(S);
	//输入字符串T 
	gets(T);
	
	int Slen=strlen(S);//字符串S的长度
	int Tlen=strlen(T);//字符串T的长度
	
	//初始化dp[i][0]和dp[0][j]
	 int i,j;
	 for(i=0;i<=Slen;i++){
	 	for(j=0;j<=Tlen;j++){
	 		dp[i][j]=INT_MAX;//初始化为最大值 
	 	}
	 	dp[i][0]=0; //当T串为0的时候S串不用修改 
	 }
	 
	 for(i=1;i<=Slen;i++){
	 	
	 	for(j=1;j<=Tlen&&i>=j;j++){//S串的长度必须大于等于T串
	 		if(S[i-1]==T[j-1]){//相等 
	 			dp[i][j]=min(dp[i-1][j-1],dp[i-1][j]);
	 		}else{//不相等 
	 			dp[i][j]=min(dp[i-1][j-1]+1,dp[i-1][j]);
	 		}
	 	}
	 	
	 } 
	
	//输出结果 
	printf("%d\n",dp[Slen][Tlen]);
	return 0;
} 

到了这里,关于蓝桥杯:最优包含--动态规划(C语言)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 独立任务的最优调度问题(动态规划)

    问题描述: 用2台处理机A和B处理n个作业。设第i个作业交给机器A处理时需要时间ai,若由机器B来处理,则需要时间bi。由于各作业的特点和机器的性能关系,很可能对于某些i,有aibi,而对于某些j,j≠i,有ajbj。既不能将一个作业分开由2台机器处理,也没有一台机器能同时处理

    2024年02月04日
    浏览(48)
  • 最优控制 3:最优控制理论中的极小值原理与动态规划

    经典变分法是一种特别强大的工具,但是它要求控制量必须可导且无界,这在很多问题中都是不成立的。着陆器的软着陆,卫星的姿态控制,等等。从主观上都可以分析出来,着陆器的软着陆控制,肯定是先让着陆器自由落体,然后从某一个高度开始反向喷气,最后落地一瞬

    2024年02月11日
    浏览(35)
  • 【最优控制笔记】——3动态规划之连续系统1

    连续系统表述为: 其性能指标写作:( 这个地方为什么是J(0)? ) 说明: 对于连续系统的动态规划问题,求解思路有两种: 1)先离散化,求解离散系统的最优控制,再利用零阶保持器制造数字控制; 2)直接解决连续最优控制问题获得连续输入 6.3.1 一般系统的离散数字控制

    2024年01月17日
    浏览(41)
  • 【动态规划】最优二叉搜索树——算法设计与分析

    二叉搜索树或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉搜索树。 规定树根为第0层,圆结点为数

    2024年02月16日
    浏览(40)
  • 基于动态规划的并联式混合动力汽车全局最优能量管理策略研究

    1.1动力系统构型 1.2车辆模型 2.1 能量管理最优问题提出 2.2 基于动态规划的能量管理策略求解        混合动力汽车由于兼具传统燃油汽车和纯电动汽车的优点,在纯电动汽车和燃料电池汽车技术尚未成熟及充电等基础设施未普及之前,成为了各国政府和汽车行业关注的重点

    2024年02月02日
    浏览(54)
  • 蓝桥杯丨动态规划

    做你想做的,错的算我的 这里是Want595,欢迎光临我的世界 ~   目录 前言  一、斐波那契式 通项公式:f(n)=f(n-1)+f(n-2)  举例说明 爬楼梯  骨牌铺方格  一只小蜜蜂 二、背包问题 通项公式:f(i,j)=max(f(i-1,j),f(i-1(或i),j-w(i))+v(i))  举例说明  0-1背包问题  完全背包问题  矿工

    2024年02月11日
    浏览(36)
  • 【蓝桥杯-筑基篇】动态规划

    🍓系列专栏:蓝桥杯 🍉个人主页:个人主页 目录 1.最大连续子段和 2.LCS 最大公共子序列 3.LIS 最长上升子序列 4.数塔 5.最大子矩阵和 6.背包问题 ①01背包问题 ②完全背包 这段代码是一个求最大子数组和的算法,使用的是动态规划的思想。下面是代码的解释: 首先定义了一个

    2023年04月24日
    浏览(72)
  • AI与控制(二)从优化到最优控制,从动态规划到强化学习--1

     优化问题,尤其静态优化问题,在控制系统设计中随处可见,例如基于燃油经济性和驾驶体验的多目标优化的汽车发动机 MAP 标定,基于性能指标优化的飞行器结构设计参数优化,以实验数据与模型输出匹配为目标的电池 RC 等效电路模型标定等等,他们都是通过构建目标函

    2024年02月02日
    浏览(43)
  • 蓝桥杯动态规划基础篇(一)

    动态规划(Dynamic Programming,DP)是运筹学的一个分支,是求解决策过程最优化的过程。20世纪50年代初,美国数学家贝尔曼(R.Bellman)等人在研究多阶段决策过程的优化问题时,提出了著名的最优化原理,从而创立了动态规划。动态规划的应用极其广泛,包括工程技术、经济、

    2024年02月03日
    浏览(38)
  • 蓝桥杯(路径 动态规划 C++)

     思路: 1、利用动态规划的思想。 2、用f[i]来记录从第一个点到第i个点的最短距离。 3、f[i]赋值分两种情况,第一种:f[i]为0的时候,也就是第一种刚到i点的情况,记录其距离为最小公倍数;第二种:f[i]已经有值了,比较新的点到其距离和之前点到其距离,取小的赋值。

    2024年02月07日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包