一、简介
动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。
虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。
在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定，它依赖于当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线．这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题称为多阶段决策问题。在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化的过程为动态规划方法
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。
以一个例子来说明动态规划的概念(leetcode第5题最长回文子串)：
给定一个字符串
s，找到s中最长的回文子串。你可以假设s的最大长度为 1000。示例 1：
输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。示例 2：
输入: "cbbd" 输出: "bb"
在这个例子中，一个字符串如果是回文子串，那么去掉头尾也照样是回文子串。而每一个字符都有可能是最长回文子串的一部分。
二、基本概念
-
多阶段决策问题
如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策（采取措施），一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称它为多阶段决策问题
各个阶段的决策构成一个决策序列，称为一个策略。每一个阶段都有若干个决策可供选择，因而就有许多策略供我们选取，对应于一个策略可以确定活动的效果，这个效果可以用数量来确定。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果 -
状态
状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。在上面的例子中状态就是某个子串是否是回文串。
-
无后效性
我们要求状态具有下面的性质：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。换句话说，过程的每一次实现可以用一个状态序列表示，在前面的例子中每阶段的状态是这个子串是否是回文串，一旦确定了这个子串的状态，在这个子串基础上的更长的字符串不受这阶段之前各段状态的影响。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性。
-
状态转移方程
给定k阶段状态变量x(k)的值后，如果这一阶段的决策变量一经确定，第k+1阶段的状态变量x(k+1)也就完全确定，即x(k+1)的值随x(k)和第k阶段的决策u(k)的值变化而变化，那么可以把这一关系看成(x(k)，u(k))与x(k+1)确定的对应关系，用x(k+1)=Tk(x(k),u(k))表示。这是从k阶段到k+1阶段的状态转移规律，称为状态转移方程。上面的例子中状态转移方程是：P(i,j)=P(i+1,j−1)∧(Si==Sj)。一个子串的状态依赖于去掉头尾之后的状态以及头尾的状态。只有去掉头尾之后是回文串并且头尾的字符相同时，这个子串才是一个回文串。
三、示例
上面这个例子使用一个二维数组表示各个阶段的状态，这个二维数组的行是子串的起始位置，列是子串的结束位置。由于j>=i，所以只需要考虑二维数组的主对角线的上半部分，对角线上的值永远是true。用true表示这个子串是回文串，false不是回文串。那么对于某个固定位置的数组元素来说，它的值依赖于左下角的元素的值。进行填充的时候只能一列一列地进行填充，同一列的元素从上到下依次填充。
给定一个字符串s="abcba"
0 1 2 3 4 0 true false false false true 1 true false true false 2 true false false 3 true false 4 true
class Solution {
public String longestPalindrome(String s) {
int len = s.length();
// 特判
if (len < 2){
return s;
}
//最大长度初始是1
int maxLen = 1;
int begin = 0;
// 1. 状态定义
// dp[i][j] 表示s[i...j] 是否是回文串
// 2. 初始化
boolean[][] dp = new boolean[len][len];
for (int i = 0; i < len; i++) {
dp[i][i] = true;
}
char[] chars = s.toCharArray();
// 3. 状态转移
// 注意：先填左下角
// 填表规则：先一列一列的填写，再一行一行的填，保证左下方的单元格先进行计算
for (int j = 1;j < len;j++){
for (int i = 0; i < j; i++) {
// 头尾字符不相等，不是回文串
if (chars[i] != chars[j]){
dp[i][j] = false;
}else {
// 相等的情况下
// 考虑头尾去掉以后没有字符剩余，或者剩下一个字符的时候，肯定是回文串
if (j - i < 3){
dp[i][j] = true;
}
//否则，判断其左下角的元素的状态
else {
// 状态转移
dp[i][j] = dp[i + 1][j - 1];
}
}
// 只要dp[i][j] == true 成立，表示s[i...j] 是否是回文串
// 此时更新记录回文长度和起始位置
if (dp[i][j] && j - i + 1 > maxLen){
maxLen = j - i + 1;
begin = i;
}
}
}
// 4. 返回值
return s.substring(begin,begin + maxLen);
}
}
网友评论