动态规划算法的入门教程：动态规划算法：（1）入门介绍及案例分析
接下来通过 最长回文子串 来加深对动态规划算法的理解。
1、问题描述：
2、思路分析：
3、代码：
- python写法：
if __name__ == "__main__":
s = input() # 输入字符串
dp = [[0 for _ in range(len(s))] for _ in range(len(s))] # dp数组初始化为0
ans = 1 # 存放结果，只有一个元素，回文子串则为1
# 边界
for i in range(len(s)-1):
dp[i][i] = 1 # 只有一个元素肯定为回文，则状态为1
if s[i] == s[i+1]:
dp[i][i+1] = 1 # 两个元素相同，则状态为1
# 状态转移方程
for L in range(3, len(s)+1): # 枚举子串的长度，从长度为3开始
for i in range(len(s)): # 枚举子串的起始端点
j = i + L - 1 # 子串的右端点
if j < len(s):
if s[i] == s[j] and dp[i+1][j-1] == 1:
dp[i][j] = 1
ans = L # 更新最长回文子串的长度
else:
break
print(ans)
结果：
- C++写法：
#include <iostream>
using namespace std;
const int maxn = 100;
int main()
{
string s;
cin >> s;
int len = s.size();
int dp[maxn][maxn] = { 0 }; //dp数组初始化为0
int ans = 1; //存放结果，只有一个元素，回文子串则为1
//边界
for (int i = 0; i < len; i++)
{
dp[i][i] = 1; //只有一个元素，回文子串则为1
if (i < len - 1)
{
if (s[i] == s[i + 1])
{
dp[i][i + 1] = 1; //两个元素
ans = 2; //两个元素，则回文子串的长度为2
}
}
}
//状态转移方程,下面是精华所在
for (int L = 3; L <= len; L++) //枚举子串的长度
{
for (int i = 0; i + L - 1 < len; i++) // 枚举子串的起始端点
{
int j = i + L - 1; //子串的右端点
if (s[i] == s[j] && dp[i + 1][j - 1] == 1)
{
dp[i][j] = 1;
ans = L; //更新最长回文子串的长度
}
}
}
cout << ans << endl;
return 0;
}
结果：
4、总结：
动态规划算法的核心在于如何设计状态转移方程，而这也是动态规划算法最难的地方。