近期笔者会写一些博客，与大家共同讨论一些经典的算法思想。这篇文章主要介绍动态规划算法的基本思想、使用动态规划算法求解问题的基本步骤、动态规划算法的两个基本要素以及一些经典的动态规划问题。
在学习动态规划之前，先思考这样一个问题：什么是动态规划？为什么叫动态规划？
当读者在试图探索这个问题的时候，不可避免的要了解动态规划的产生背景。动态规划是由 Dynamic Programming 翻译过来的。动态规划的概念是由美国数学家R.E.Bellman等人提出的，应用于工程领域。
动态规划是是求解多阶段决策过程(decision process)的最优化问题一种方法。
所谓多阶段决策过程是指这样一类决策过程：它可以把一一个复杂问题按时间(或空间)分成若干个阶段，每个阶段都需要作出决策，
以便得到过程的最优结局。由于在每阶段采取的决策是与时间有关的而且前一阶段采取的决策如何，不但与该阶段的经济效果有关，
还影响以后各阶段的经济效果，可见这类多阶段决策问题是一个动态的问题，因此，处理的方法称为动态规划方法。然而，动态
规划也可以处理一些本来与时间没有关系的静态模型，这只要在静态模型中人为地引入“时间”因素，分成时段，就可以把它看作
是多阶段的动态模型，用动态规划方法去处理。
简言之，多阶段决策过程是指这样的一类特殊的活动过程：问题可以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。
下面举例说明什么是多阶段决策问题。
例1（最短路线问题）在线路网络图1中，从A至E有一批货物需要调运。图上所标数字为各节点之间的运输距离，为使总运费最少，必须找出一条由A至E总里程最短的路线。
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。
但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。
如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。
a. 找出最优解的性质，并刻划其结构特征。
b. 递归地定义最优值。
c. 以自底向上的方式计算出最优值。
d. 根据计算最优值时得到的信息，构造最优解
注意：同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）
题目描述：
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
分析：
一个问题要使用动态规划求解，一定要满足【最优子结构】，只有满足最优子结构，才能通过子问题的解 构造出 整个问题的解。
在编码时，一般采用【备忘录】或 dp table来实现。
最关键的要找出：该问题的递推关系式（状态转移方程）
假设dp[i][j]=true,表示字符串s从s[i]到s[j]的子串为最长回文子串
反之false.
考虑 abcba 这个示例。如果我们已经知道 bca 是回文，那么要判断 abcba 是不是回文串，只需判断它的左首字母和右尾字母是否相等。这里左=右=a，因此abcba 是回文串
从这里我们可以归纳出状态转移方程
dp[i][j] = true
前提是
dp[i+1][j-1]为true,且 s[i] == s[j]
#include <iostream>
using namespace std;
class MySolution {
public:
string longestPalindrome(string s) {
int len = s.size();
if (len < 2)
return s;
//bool dp[len][len];
bool** dp;
dp = new bool* [len];
for (int i = 0; i < len; i++)
dp[i] = new bool[len];//分配了len行len列的二维数组空间
int max_len=1;//最大回文串长度
int max_left;//最长回文串的起始位置
for (int j = 0; j < len; j++)
{
for (int i = 0; i < j; i++)
{
if (s[j] != s[i])
dp[i][j] = false;
else if (j - i < 3) // (j-1)-(i+1)+1< 2 即表明dp[i][j]是回文串
dp[i][j] = true;
else
dp[i][j] = dp[i + 1][j - 1];//s[i]==s[j]
if (j - i + 1 > max_len && dp[i][j])
{
max_len = j - i + 1;
max_left = i;
}
}
}
return s.substr(max_left, max_len);
// 用完要释放:
for (int i = 0; i < len; i++)
{
delete[] dp[i];
delete[]dp;
}
}
};
int main()
{
MySolution sl;
string s = sl.longestPalindrome("abcdedcabcdefggfedcba");
cout << s << endl;
}
参考文献
[1] 引用自百度文库https://wenku.baidu.com/view/c0f9fb156c175f0e7cd1377d.html
[2]引用自老师的课件