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