基础算法之动态规划

动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。
把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,属于过程优化的范畴,在现在的很多程序处理过程中广泛运用,直接正题吧,概念性的可以百度更深入了解,
今天我先来点简单的例子:

来一道题:找出给定字符串中的最长回文串;
回文串:即对称串,比如aaabbb、adda、a,除了字符本身外,回文串一定是偶数个字符,是基于中心对称的.
我们试试最常规的写法(暴力):
遍历每一个起始位置,再遍历每一个结束位置,再遍历每一个起始到结束位置的字符判断是不是回文,balabalalalalalalalla….时间复杂度O(n^3)
还是放弃吧…

下面看看动态规划的处理方式:
dp[i][j]=0表示子串[i,j]不是回文串。dp[i][j]=1表示子串[i,j]是回文串
则:
状态转移方程:dp[i,j]{=dp[i+1,j-1],if(s[i]==s[j]) || =0,if(s[i]!=s[j])}

我们把当前状态转移到了他的子集,这样就好处理了许多;

public static void main(String[] args) {
String s = “aaabbbbbbaaasss”;
if(s.length() <=1) //字符长度小于等于1,直接输出
System.out.println(s);
int maxLength = 0;
int start = 0;//记录最长回文串的开始位置
int[][] dp = new int[s.length()][s.length()];//二维数组,用于状态转移
for (int i = 0; i < s.length(); i++) {//初始化能保证[i,i]第i个位置到第i个位置即单个字符一定是回文串,如果[i,i+1]也等的话也一并初始化
dp[i][i] = 1;
if(i<s.length()-1 && s.charAt(i)==s.charAt(i+1))
{
dp[i][i+1]=1;
start=i;
maxLength=2;
}
}
for (int l = 3; l <= s.length(); l++) {//遍历所有的子串长度
for (int i = 0; i <= s.length()-l; i++) {//遍历所有长度的起始位置
int j = i + l – 1;//那么计算出子串的结束位置就该是它了
if(dp[i+1][j-1] == 1 && s.charAt(i)==s.charAt(j)){//对每个子串向前回溯,如果当前的起止位置字符相等并且向里缩进的子串是回文串,那么当前的起止串一定也是回文串
dp[i][j]=1;//当前的起止串标记为回文串
maxLength=l;//记录最大长度(如果有更长的,之前的就会被覆盖)
start=i;//记录每个长度的起始位置
}
}
}
if(maxLength >= 2)
System.out.println(s.substring(start,maxLength));
else
System.out.println(“没有最长回文!!!”);
}
动态规划处理这个问题的时间复杂度O(n^2),比之前快了很多,但是这个例子不够形象,我们从最简单的地方入手:

我们看一个数塔问题:TIM图片20170913144601

图片不清晰,再描述下问题:要求从顶层走到底层,若每一步只能走到相邻的结点,则经过的结点的数字之和最大是多少?
状态转移方程dp [i] = max(dp[左孩子] , dp[右孩子]) + dp[i]
public static void main(String[] args) {
int[][] dp= {//初始化数塔
{9,0,0,0,0},
{12,15,0,0,0},
{10,6,8,0,0},
{2,18,9,5,0},
{19,7,10,4,16}
};
for(int i = 4; i > 0; i–) {
for (int j = 0; j < i; j++) {
dp[i – 1][j] += dp[i][j] > dp[i][j + 1] ? dp[i][j] : dp[i][j + 1];//如果左边比右边大,那么只加左孩子,反之加右孩子
//每次加完之后的值都会赋给上一层,直到dp[0][0],这样总能保证和最大
}
}
System.out.println(dp[0][0]);
}

暂时就这些吧,下次再补充~~~

《基础算法之动态规划》有6个想法

    1. 嗯嗯,之前在很多程序处理的地方用到过,有些复杂的问题这样分阶段去处理,类似于分治的思想,后面处理就会很容易,代码也不会复杂~

发表评论

电子邮件地址不会被公开。 必填项已用*标注