经典算法系(7)-动态规划(Dynamic Programming)
8. 动态规划(Dynamic Programming)
DP主要用于解决包含重叠子问题(Overlapping Subproblems)的最优化问题,其基本策略是将原问题分解为相似的子问题,通过求解并保存最简单子问题的解,然后逐步合并成为原问题的解,由于需要查询子问题的解,所以需要一个表格记录子问题的解;DP仅适用于最优子结构问题(Optimal Substructure),也就是局部最优解相当于(或者近似于)全局最优解;
对于原问题而言,当递归地自顶向下对问题进行求解时,每次产生的子问题可能与之前差生的子问题重复(如Fibonacci数列的求解);DP通过自底向上求解子问题的解并将其保存在一个表格中,当再次遇到相同子问题时就直接通过查表得到其解(分治算法的子问题则是完全独立子空间);使用DP之前需要判定当前问题是否具有下述三个特性:
最优子结构:无论之前的状态和决策如何,当前的局部最优解是构成全局最优解的必要条件
无后效性:对于某个给定的阶段状态而言,在此之前的所有决策和状态都无法直接影响未来的决策,而只能通过当前的决策和状态影响
空间需求度:DP实际上是一种空间换时间的策略,在求解的过程中需要不断存储子问题的解并提供合理的查询方式
DP的四个步骤
划分阶段:注意划分之后的阶段必须是有序或者可排序的
确定状态和状态变量:将划分后的子问题使用不同状态表示,并满足无后效性
确定决策并写出状态转移方程:根据相邻两个阶段的状态关系得出转移方程
寻找边界条件:给出的转移方程是一个递归式,需要最终确定一个终止条件
最长公共子序列的DP解法
LCS问题与LIS(Largest Incremental Sub-sequence)问题类似,将原字符串A进行排序之后得到B,则A的LIS就是A和B的LCS。另外也可以直接使用DP。
解法1:Largest Common Sub-string,如果将需求理解为公共子串的字符必须相连,则解法如下:将字符串A的每一个字符依次匹配B的每一个位置,时间复杂度O(MN),M和N分别为A和B的长度,同样也可以使用DP填表的方式求解。KMP算法也可以求解,时间复杂度为O(M+N)
解法2:Largest Common Sub-Sequence,如果将需求理解为公共子串的字符可以分离,则为经典的LCS问题(也可以理解为求两个集合的顺序交集),则解法如下:动态规划(DP),动态规划一般应用于具有最优子结构的问题,也就是局部最优解可以决定全局最优解;动态规划的关键点在问题的拆分和状态关系的转移;
给定first[1,m]和second[1,n],求LCS(first[1,m],second[1,n]),
如果first和second的最后一个字符相同,则有first[m]=second[n]=result[k],这样问题化解为给定first[1,m-1]和second[1,n-1],求LCS(first[1,m-1],second[1,n-1]),原问题转化为LCS(first[1,m],second[1,n])= LCS(first[1,m-1],second[1,n-1]) +1
如果first和second的最后一个字符不相同,则问题化解为result[1,k]= max{LCS(first[1,m-1],second[1,n]), LCS(first[1,m],second[1,n-1])
/**
* 利用动态规划,使用簿记matrix的方法记录小子问题,然后重复利用
* 小子问题解决合成问题,最终解决整个问题。
* 在first和second组成的二维表中,一共有三种状态转移方式:
* 如果first[m]=second[n],则跳到first[m-1]和second[n-1]
* 如果first[m]!=second[n],则跳到first[m-1]和second[n],
* first[m]和second[n-1]的LCS中较大的一个
* 需要设定初始状态为0
* */
void lcs2(char *first, int lfirst, char *second, int lsecond) {
int *dir=new int[lfirst*lsecond];
int *dis=new int[lfirst*lsecond];
/**
* 保留first和second的第一个字符,将其dis设置为0,便于实现簿记
* dir矩阵中:0表示up-left移动;1表示left移动;2表示up移动
* */
for(int i=0;i<lfirst;i++)
dis[i]=0;
for(int i=0;i<lsecond;i++)
dis[i*lfirst]=0;
for(int j=1;j<lsecond;j++) {
for(int i=1;i<lfirst;i++) {
if(first[i]==second[j]) {
/**
* 如果当前字符相等,则说明[i,j]长度的LCS为
* [i-1,j-1]长度的LCS 加上1;
* up-left移动
* */
dis[i+j*lfirst]=
dis[(i-1)+(j-1)*lfirst]+1;
dir[i+j*lfirst]=0;
} else if(dis[i+(j-1)*lfirst] >
dis[(i-1)+j*lfirst]) {
/**
* 如果当前字符不等,并且[i,j-1]长度的LCS大于
* [i-1,j]长度的LCS,则当前[i,j]长度的LCS等于
* [i,j-1]产度的LCS
* up移动
* */
dis[i+j*lfirst]=
dis[i+(j-1)*lfirst];
dir[i+j*lfirst]=2;
} else {
/**
* 如果当前字符不等,并且[i-1,j]长度的LCS大于
* [i,j-1]长度的LCS,则当前[i,j]长度的LCS等于
* [i-1,j]产度的LCS
* left移动
* */
dis[i+j*lfirst]=
dis[(i-1)+j*lfirst];
dir[i+j*lfirst]=1;
}
}
}
showLCS(first, dir, lfirst-1, lsecond-1, lfirst);
delete [] dir;
delete [] dis;
}
背包问题的DP解法
参考连接:
http://blog.csdn.net/v_july_v/article/details/6695482
http://en.wikipedia.org/wiki/Dynamic_programming
http://blog.csdn.net/sharpdew/article/details/763180
DP主要用于解决包含重叠子问题(Overlapping Subproblems)的最优化问题,其基本策略是将原问题分解为相似的子问题,通过求解并保存最简单子问题的解,然后逐步合并成为原问题的解,由于需要查询子问题的解,所以需要一个表格记录子问题的解;DP仅适用于最优子结构问题(Optimal Substructure),也就是局部最优解相当于(或者近似于)全局最优解;
对于原问题而言,当递归地自顶向下对问题进行求解时,每次产生的子问题可能与之前差生的子问题重复(如Fibonacci数列的求解);DP通过自底向上求解子问题的解并将其保存在一个表格中,当再次遇到相同子问题时就直接通过查表得到其解(分治算法的子问题则是完全独立子空间);使用DP之前需要判定当前问题是否具有下述三个特性:
最优子结构:无论之前的状态和决策如何,当前的局部最优解是构成全局最优解的必要条件
无后效性:对于某个给定的阶段状态而言,在此之前的所有决策和状态都无法直接影响未来的决策,而只能通过当前的决策和状态影响
空间需求度:DP实际上是一种空间换时间的策略,在求解的过程中需要不断存储子问题的解并提供合理的查询方式
DP的四个步骤
划分阶段:注意划分之后的阶段必须是有序或者可排序的
确定状态和状态变量:将划分后的子问题使用不同状态表示,并满足无后效性
确定决策并写出状态转移方程:根据相邻两个阶段的状态关系得出转移方程
寻找边界条件:给出的转移方程是一个递归式,需要最终确定一个终止条件
最长公共子序列的DP解法
LCS问题与LIS(Largest Incremental Sub-sequence)问题类似,将原字符串A进行排序之后得到B,则A的LIS就是A和B的LCS。另外也可以直接使用DP。
解法1:Largest Common Sub-string,如果将需求理解为公共子串的字符必须相连,则解法如下:将字符串A的每一个字符依次匹配B的每一个位置,时间复杂度O(MN),M和N分别为A和B的长度,同样也可以使用DP填表的方式求解。KMP算法也可以求解,时间复杂度为O(M+N)
解法2:Largest Common Sub-Sequence,如果将需求理解为公共子串的字符可以分离,则为经典的LCS问题(也可以理解为求两个集合的顺序交集),则解法如下:动态规划(DP),动态规划一般应用于具有最优子结构的问题,也就是局部最优解可以决定全局最优解;动态规划的关键点在问题的拆分和状态关系的转移;
给定first[1,m]和second[1,n],求LCS(first[1,m],second[1,n]),
如果first和second的最后一个字符相同,则有first[m]=second[n]=result[k],这样问题化解为给定first[1,m-1]和second[1,n-1],求LCS(first[1,m-1],second[1,n-1]),原问题转化为LCS(first[1,m],second[1,n])= LCS(first[1,m-1],second[1,n-1]) +1
如果first和second的最后一个字符不相同,则问题化解为result[1,k]= max{LCS(first[1,m-1],second[1,n]), LCS(first[1,m],second[1,n-1])
/**
* 利用动态规划,使用簿记matrix的方法记录小子问题,然后重复利用
* 小子问题解决合成问题,最终解决整个问题。
* 在first和second组成的二维表中,一共有三种状态转移方式:
* 如果first[m]=second[n],则跳到first[m-1]和second[n-1]
* 如果first[m]!=second[n],则跳到first[m-1]和second[n],
* first[m]和second[n-1]的LCS中较大的一个
* 需要设定初始状态为0
* */
void lcs2(char *first, int lfirst, char *second, int lsecond) {
int *dir=new int[lfirst*lsecond];
int *dis=new int[lfirst*lsecond];
/**
* 保留first和second的第一个字符,将其dis设置为0,便于实现簿记
* dir矩阵中:0表示up-left移动;1表示left移动;2表示up移动
* */
for(int i=0;i<lfirst;i++)
dis[i]=0;
for(int i=0;i<lsecond;i++)
dis[i*lfirst]=0;
for(int j=1;j<lsecond;j++) {
for(int i=1;i<lfirst;i++) {
if(first[i]==second[j]) {
/**
* 如果当前字符相等,则说明[i,j]长度的LCS为
* [i-1,j-1]长度的LCS 加上1;
* up-left移动
* */
dis[i+j*lfirst]=
dis[(i-1)+(j-1)*lfirst]+1;
dir[i+j*lfirst]=0;
} else if(dis[i+(j-1)*lfirst] >
dis[(i-1)+j*lfirst]) {
/**
* 如果当前字符不等,并且[i,j-1]长度的LCS大于
* [i-1,j]长度的LCS,则当前[i,j]长度的LCS等于
* [i,j-1]产度的LCS
* up移动
* */
dis[i+j*lfirst]=
dis[i+(j-1)*lfirst];
dir[i+j*lfirst]=2;
} else {
/**
* 如果当前字符不等,并且[i-1,j]长度的LCS大于
* [i,j-1]长度的LCS,则当前[i,j]长度的LCS等于
* [i-1,j]产度的LCS
* left移动
* */
dis[i+j*lfirst]=
dis[(i-1)+j*lfirst];
dir[i+j*lfirst]=1;
}
}
}
showLCS(first, dir, lfirst-1, lsecond-1, lfirst);
delete [] dir;
delete [] dis;
}
背包问题的DP解法
参考连接:
http://blog.csdn.net/v_july_v/article/details/6695482
http://en.wikipedia.org/wiki/Dynamic_programming
http://blog.csdn.net/sharpdew/article/details/763180
热门话题 · · · · · · ( 去话题广场 )
- 你画大家猜(猜电影) 48.1万次浏览
- 我这偷感十足的一生 5.9万次浏览
- 你有哪些保持精力充沛的方法? 9.1万次浏览
- 我们为什么需要书店? 4.3万次浏览
- 电视剧中的尴尬台词 4102次浏览
- 淡人穿搭实录 新话题