C++動態(tài)規(guī)劃之最長公子序列實(shí)例
更新時間：2015年04月20日 12:27:22 作者：司青
這篇文章主要介紹了C++動態(tài)規(guī)劃之最長公子序列,實(shí)例分析了C++求最長公子序列的相關(guān)技巧,是C++字符串操作的一個典型應(yīng)用,需要的朋友可以參考下
本文實(shí)例講述了C++動態(tài)規(guī)劃之最長公子序列解決方法。分享給大家供大家參考。具體分析如下：
問題描述：
求出兩個字符串中的最長公子序列的長度。
輸入：
csblog
belong
輸出：
max length = 4
實(shí)現(xiàn)代碼：
#include <stdio.h>
#include <string.h>
int arr[200][200];
/* 表示str1的前i位和str2的前j位的最長公子序列的長度 */
int main()
{
char str1[100],str2[100];
/* 輸入數(shù)據(jù) */
scanf("%s%s",str1,str2);
int len1 = strlen(str1);
int len2 = strlen(str2);
/* 初始化數(shù)組 */
int i,j;
for(i = 0 ; i <= len1 ; ++i)
{
for(j = 0 ; j <= len2 ; ++j)
arr[i][j] = 0;
}
/* 計算 */
for(i = 1 ; i <= len1 ; ++i)
{
for(j = 1 ; j <= len2 ; ++j)
{
/* 字符相同，則最長公子序列長度加1 */
if(str1[i - 1] == str2[j - 1])
{
arr[i][j] = arr[i - 1][j - 1] + 1;
}
else
/* 當(dāng)前字符不相同，則取上次選擇的最大值做為當(dāng)前結(jié)果 */
{
arr[i][j]=arr[i][j-1]>arr[i-1][j]?arr[i][j-1]:arr[i-1][j];
}
}
}
/* 輸出結(jié)果 */
printf("max length = %d\n",arr[len1][len2]);
return 0;
}
希望本文所述對大家的C++程序設(shè)計有所幫助。
相關(guān)文章
本文主要介紹了淺談C++不同繼承之間的關(guān)系，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-04-04
C++函數(shù)三種傳參形式(指針傳遞、引用傳遞、值傳遞)
不論是哪種參數(shù)傳遞方式,都有形參和實(shí)參之分,本文主要介紹了C++函數(shù)三種傳參形式(指針傳遞、引用傳遞、值傳遞),具有一定的參考價值,感興趣的可以了解一下2024-03-03
C++ OpenCV實(shí)戰(zhàn)之制作九宮格圖像
本文將為大家介紹如何使用OpenCV C++ 制作九宮格圖像，即將一張圖像均等分成九份，然后將這九個小塊按一定間隔拷貝到新畫布上就可以啦。感興趣的可以動手試一試2022-01-01
本篇文章介紹了，如何在TC2.0中調(diào)用匯編程序的解決方法。需要的朋友參考下2013-05-05
這篇文章主要介紹了使用C++調(diào)用Python代碼并給大家介紹了.py和.pyc的區(qū)別，本文給大家介紹的非常詳細(xì)，具有一定的參考借鑒價值，需要的朋友可以參考下2020-02-02
C++實(shí)現(xiàn)LeetCode(106.由中序和后序遍歷建立二叉樹)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(106.由中序和后序遍歷建立二叉樹),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
大家好，本篇文章主要講的是C語言用遞歸函數(shù)實(shí)現(xiàn)漢諾塔，感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下2022-01-01
這篇文章主要介紹了c語言小游戲程序之彈跳小球的實(shí)現(xiàn)代碼,本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-12-12
VisualStudio2019構(gòu)建C/C++靜態(tài)庫和動態(tài)庫dll的問題 附源碼
這篇文章主要介紹了VisualStudio2019構(gòu)建C/C++靜態(tài)庫和動態(tài)庫(dll)(文末附源碼),本文通過實(shí)例圖文相結(jié)合給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-03-03
strcat是用來拼接字符串的，它會將參數(shù)?src?字符串復(fù)制到參數(shù)?dest?所指的字符串尾部，本章帶你了解它的使用并模擬實(shí)現(xiàn)它2022-05-05