这儿有两种方法处理,一个称为自顶向下,另一个称为自下向顶.前者称为可记忆化,后者被称为动态。
在动态规划中,所有的子问题(即使没用到的)被解决,但是在递归中,只有要求到的子问题被解决。
这个问题是从一个给定的字符串中,找到一个最大的上升子序列。 很经典的dp,状态转移方程
Opt[i]=max{1,Opt[j]+1};{A[j]<=A[i],1<=j<i}
其实自己连什么是LIS都不知道,是指序列中从小到大的个数,不用管其在序列上是否为连续的。
L(i)={1+Max(L(j))} where j<i and arr[j]<arr[i] and if there is no such j then L(i)=1
我的问题是自己能隐隐约约体会到其中一点的转移,但是在代码实现上就麻烦了,自己 始终不能流畅的写出来。最后想了想,其实上面的状态转移方程还是不太容易理解,网上有个是这么说的maxlen[i]=(max(maxlen[k],1,2,3..k..i-1&&str[k]<str[i])+1) a下面代码中m可以堪看成临时变量temp,它的作用就是搜索maxlen[i]前面最大的dp[i] ,想明白了这道,hdu 1087也就1y了
已经过去很长时间了,算法这块的难处还是很难啃的。正如上面讲的,自己最欠缺的地方是如何将状态转移方程写成代码的能力,这一点不是其他外力就能控制的。
伪代码如下:
LS[1] = 1 for i from 1 to n m=LS[i] for j from i-1 to 0 a[i]>a[j] && LS[j]>m m=LS[i]; LS[i]=m+1 max{LS[i]}
/*
* File Name: dp_lis.c
* Author: Bo Yu
* Mail: [email protected]
* Created Time: 2016年08月18日 星期四 02时52分56秒
*/
/*
* 关于动态规划的入门题
* 求一个数列的最大上升子序列
状态方程:
*L(i) = { 1 + Max ( L(j) ) }
where j < i and arr[j] < arr[i] and if there is no such j then L(i) = 1
*
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int LS[100];
int LIS(int a[], int n)
{
int ans = 1, m, i, j;
LS[1] = 1;
for(i = 1; i < n; i++){
m = LS[i];/*Reset m==0 */
for( j = i - 1; j >= 0; j --)
if(a[j] < a[i] && LS[j] > m)
m = LS[j]; /*寻到前面的最大LIS*/
/*从前面(i-1)个LS中加上1*/
LS[i] = m + 1;
/*找寻最大的LS*/
if (LS[i] > ans)
ans = LS[i];
}
return ans;
}
int main()
{
int a[10] = {10, 22, 9, 33, 21, 50, 41, 60, 80};
/*int a[20] = {5,7,6,1,3,9,5,3,4,1,4,5,6,7,8};*/
memset(LS, 0, sizeof(LS));
int k = LIS(a, 9);
printf("THE LIS is %d\n", k);
}
代码时间复杂度是O(n^2),并且n<=12000,并不是最优的。
#简单的总结
现在已经是2014年7月15日,放假已经快两周了,现在的练习怎么样了,只能由自己慢慢体会了。不过,今天倒是在动态规划的LIS理解上给自己一针鸡血,希望自己继续努力下去。 现在开始看01背包
很简单的一道动态规划,而且没有打印路径 我的思路也是来自《算法导论》,但是看了一个台湾朋友的博客才算是明白了一点点。 他是这么想的,将两个字符串各取最后一个的e1,e2,这样原字符串可以表示为sub1+e1,sub2+e2,
后来再补充!
#关于本博客
首先,感谢我的同学–刘欢,这个模板就是copy他的repo,回想从大一伊始,他没少在计算机的路上带我,感谢!!! 为了表达对它的敬意,他前面的文章我保留了,在2014-07之前,本博客所写的文章均出自bitsly,转载请注明。