中级动态规划算法——C++实现经典案例_动态规划的c++代码

中级动态规划算法——C++实现经典案例

动态规划（Dynamic Programming，DP）是一种解决多阶段决策过程最优化问题的方法。本文将介绍几个经典的动态规划问题，并给出C++语言的实现代码。

1. 斐波那契数列
   斐波那契数列是一个非常经典的递归问题，其定义为f(n)=f(n-1)+f(n-2)，其中f(0)=0，f(1)=1。由于递归调用会造成大量的重复计算，因此可以使用动态规划的思想来避免这种情况。

C++代码如下：

int Fibonacci(int n)
{
if (n < 2)
return n;
int f1 = 0, f2 = 1, f3 = 1;
for (int i = 2; i <= n; ++i)
{
f3 = f1 + f2;
f1 = f2;
f2 = f3;
}
return f3;
}

2. 最长公共子序列
   给定两个字符串S和T，求它们的最长公共子序列（Longest Common Subsequence，LCS）。例如，S=“ABCD”，T=“BD”，则它们的最长公共子序列为"BD"。

C++代码如下：

int LCS(string S, string T)
{
int m = S.size(), n = T.size();
vector&