C++怎么实现一个动态规划算法_C++解决最长公共子序列(LCS)等经典DP问题

尼克

发布时间：2025-11-22 15:21:35

335人浏览过

来源于php中文网

原创

答案：动态规划通过状态转移求解最优化问题，以LCS为例，定义dpi为两字符串前i和前j字符的最长公共子序列长度，若字符相等则dpi=dpi-1+1，否则dpi=max(dpi-1, dpi)，初始条件为边界全0；C++使用vector构建DP表并双重循环填充，最终返回dpm即为长度，可通过反向追踪还原LCS字符串，该方法适用于重叠子问题与最优子结构的场景。

c++怎么实现一个动态规划算法_c++解决最长公共子序列(lcs)等经典dp问题

动态规划（Dynamic Programming，简称DP）是C++中解决最优化问题的重要方法，尤其适用于具有重叠子问题和最优子结构性质的问题。最长公共子序列（LCS）就是典型的例子。下面以LCS为例，说明如何用C++实现一个动态规划算法。

理解LCS问题

给定两个字符串 str1 和 str2，找出它们的最长公共子序列的长度。子序列不要求连续，但要保持字符在原串中的相对顺序。

例如：
str1 = "ABCDGH"
str2 = "AEDFHR"
LCS 是 "ADH"，长度为 3。

定义状态与状态转移方程

使用二维数组 dp[i][j] 表示 str1 的前 i 个字符和 str2 的前 j 个字符的 LCS 长度。

状态转移逻辑如下：

立即学习“C++免费学习笔记（深入）”；

OneAI

将生成式AI技术打包为API，整合到企业产品和服务中

下载

如果 str1[i-1] == str2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1
否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])

初始条件：dp[0][j] = 0，dp[i][0] = 0，表示空串与任何串的 LCS 为 0。

C++代码实现

#include 
#include 
#include 
#include 
using namespace std;

int longestCommonSubsequence(string str1, string str2) {
    int m = str1.length();
    int n = str2.length();

    // 创建二维DP表
    vector> dp(m + 1, vector(n + 1, 0));

    // 填充DP表
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (str1[i-1] == str2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }

    return dp[m][n];
}

// 测试函数
int main() {
    string s1 = "ABCDGH";
    string s2 = "AEDFHR";
    cout << "LCS Length: " << longestCommonSubsequence(s1, s2) << endl;
    return 0;
}

输出LCS字符串本身

如果不仅要长度，还想还原出具体的子序列，可以从 dp[m][n] 开始反向追踪：

string getLCSString(string str1, string str2, vector>& dp) {
    string lcs = "";
    int i = str1.length(), j = str2.length();

    while (i > 0 && j > 0) {
        if (str1[i-1] == str2[j-1]) {
            lcs = str1[i-1] + lcs;
            i--; j--;
        } else if (dp[i-1][j] > dp[i][j-1]) {
            i--;
        } else {
            j--;
        }
    }
    return lcs;
}

只需在主函数中调用该函数即可得到实际的LCS字符串。

基本上就这些。掌握状态定义、转移方程和边界处理，就能应对大多数经典DP问题，比如背包问题、编辑距离、最大子数组和等。关键在于把复杂问题拆解成可递推的小问题，并用表格避免重复计算。C++的vector和循环控制让实现变得简洁高效。

CSS中隐藏滚动条的同时保留滚动功能

CSS 布局技巧实现元素左右排列的方法

CSS给div一个带有圆角的渐变边框效果

HTML5使用details标签：展开/收缩信息

CSS Grid 布局在 IE 中不兼容的原因及解决方案

相关标签:

css go ai c++ ios stream 字符串循环算法

本站声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

上一篇：c++中模板特化和偏特化是什么_C++模板高级特性与使用场景下一篇：C++的RTTI(运行时类型信息)是什么_C++中dynamic_cast与typeid的底层原理

作者最新文章

Win11怎么启用深色模式_Win11全局暗黑主题设置方法【个性化】

2026-01-17 19:30

Windows如何解决打印机后台处理服务未运行的问题？

2026-01-17 19:36

Win11怎么设置默认日历提醒声音_Win11事件通知铃声自定义更换【办公】

2026-01-17 19:39

怎么用ai创作有声书_AI文本转语音与情感旁白制作指南

2026-01-17 19:42

Win11怎么启用系统低功耗模式强制开启_Win11延长笔记本续航设置【省电】

2026-01-17 19:47

Win11怎么关闭自动更新_Win11暂停更新永久设置【系统】

2026-01-17 19:59

怎么用ai做游戏角色设计_AI游戏原画概念与三视图生成法

2026-01-17 20:07

怎么用ai做思维导图_AI逻辑梳理与结构图一键成图指南

2026-01-17 20:13

如何制作一个U盘便携版的谷歌浏览器？免安装浏览器制作教程

2026-01-17 20:29

如何关闭Edge浏览器的购物功能和优惠券提示？微软浏览器购物助手关闭教程

2026-01-17 20:35

热门AI工具

DeepSeek

幻方量化公司旗下的开源大模型平台

AI大模型

开放平台

豆包大模型

字节跳动自主研发的一系列大型语言模型

AI大模型

通义千问

阿里巴巴推出的全能AI助手

AI大模型

腾讯元宝

腾讯混元平台推出的AI助手

文档处理

Excel 表格

文心一言

文心一言是百度开发的AI聊天机器人，通过对话可以生成各种形式的内容。

AI大模型

中文写作

讯飞写作

基于讯飞星火大模型的AI写作工具，可以快速生成新闻稿件、品宣文案、工作总结、心得体会等各种文文稿

中文写作

写作工具

即梦AI

一站式AI创作平台，免费AI图片和视频生成。

图片拼接

图画生成

ChatGPT

最最强大的AI聊天机器人程序，ChatGPT不单是聊天机器人，还能进行撰写邮件、视频脚本、文案、翻译、代码等任务。

AI大模型

中文写作

智谱清言 - 免费全能的AI助手

AI大模型

PDF 文档

相关专题

js 字符串转数组

js字符串转数组的方法：1、使用“split()”方法；2、使用“Array.from()”方法；3、使用for循环遍历；4、使用“Array.split()”方法。本专题为大家提供js字符串转数组的相关的文章、下载、课程内容，供大家免费下载体验。

258

2023.08.03

js截取字符串的方法

js截取字符串的方法有substring()方法、substr()方法、slice()方法、split()方法和slice()方法。本专题为大家提供字符串相关的文章、下载、课程内容，供大家免费下载体验。

208

2023.09.04

java基础知识汇总

java基础知识有Java的历史和特点、Java的开发环境、Java的基本数据类型、变量和常量、运算符和表达式、控制语句、数组和字符串等等知识点。想要知道更多关于java基础知识的朋友，请阅读本专题下面的的有关文章，欢迎大家来php中文网学习。

1465

2023.10.24

字符串介绍

字符串是一种数据类型，它可以是任何文本，包括字母、数字、符号等。字符串可以由不同的字符组成，例如空格、标点符号、数字等。在编程中，字符串通常用引号括起来，如单引号、双引号或反引号。想了解更多字符串的相关内容，可以阅读本专题下面的文章。

619

2023.11.24

java读取文件转成字符串的方法

Java8引入了新的文件I/O API，使用java.nio.file.Files类读取文件内容更加方便。对于较旧版本的Java，可以使用java.io.FileReader和java.io.BufferedReader来读取文件。在这些方法中，你需要将文件路径替换为你的实际文件路径，并且可能需要处理可能的IOException异常。想了解更多java的相关内容，可以阅读本专题下面的文章。

550

2024.03.22