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++程序設計有所幫助。
相關文章
這篇文章主要為大家介紹了QT中線程池QThreadPool類概念和使用方法詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-09-09
靜態(tài)鏈表和動態(tài)鏈表是線性表鏈式存儲結構的兩種不同的表示方式。靜態(tài)鏈表的初始長度一般是固定的，在做插入和刪除操作時不需要移動元素，僅需修改指針。動態(tài)鏈表是相對于靜態(tài)鏈表而言的，一般地，在描述線性表的鏈式存儲結構時如果沒有特別說明即默認描述的是動態(tài)鏈表。2016-05-05
本文主要介紹了C++二叉搜索樹模擬實現示例,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2023-11-11
這篇文章主要為大家詳細介紹了C++利用鏈表實現圖書信息管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-11-11
這篇文章主要介紹了VC運用OPENGL加載BMP紋理圖的實現方法,對于更好的了解OpenGL很有幫助,需要的朋友可以參考下2014-07-07
Shellcode是一種獨立于應用程序的機器代碼,通常用于實現特定任務,如執(zhí)行遠程命令、注入惡意軟件或利用系統(tǒng)漏洞,本文將深入探討如何在C語言中提取Shellcode,并通過XOR加密技術增加其混淆程度,文中通過代碼示例講解的非常詳細,需要的朋友可以參考下2023-12-12
大小端是內存存儲字節(jié)的兩種方式,一個是大端存儲,一個是小端存儲,本文主要介紹了c語言大小端,具有一定的參考價值,感興趣的可以了解一下2023-09-09
大家好，本篇文章主要講的是用c語言實現一個電話?。ǜ酵暾a），感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下，方便下次瀏覽2022-01-01
本文主要介紹了各種API遠程線程注入的方法，分別是 遠程線程注入，普通消息鉤子注入，全局消息鉤子注入，APC應用層異步注入，ZwCreateThreadEx強力注入，純匯編實現的線程注入等2021-06-06
以下是分別是對new和malloc的區(qū)別進行了詳細的分析及介紹，需要的朋友可以過來參考下2013-09-09