这儿有两种方法处理，一个称为自顶向下，另一个称为自下向顶.前者称为可记忆化，后者被称为动态。
在动态规划中，所有的子问题(即使没用到的)被解决，但是在递归中，只有要求到的子问题被解决。
LIS(最大上升子序列)
这个问题是从一个给定的字符串中，找到一个最大的上升子序列。 很经典的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了
2016.08.18
已经过去很长时间了，算法这块的难处还是很难啃的。正如上面讲的，自己最欠缺的地方是如何将状态转移方程写成代码的能力，这一点不是其他外力就能控制的。
伪代码如下：
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,并不是最优的。
hdu 1087
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
int dp[1001];//less than 12000
int a[1001];
int LIS(int* a,int n)
{
int ans=1,m//m是临时变量;
dp[1]=1;
for(int i=2;i<=n;i++)
{
m=dp[i];//?
for(int j=i-1;j>=1;j--)
if((a[j]<a[i])&&(dp[j]>m))
m=dp[j];
dp[i]=m+1;
if(dp[i]>ans)
ans=dp[i];
}
return ans;
}
int main()
{
freopen("in.txt","r",stdin);
int k;
int n;
scanf("%d",&k);//数据组数
while(k--){
memset(a,0,sizeof(a));
memset(dp,0,sizeof(dp));
scanf("%d",&n);//每组数列的个数
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
int k=LIS(a,n);
printf("%d\n",k);
}
}LCS
01背包
假设有一个背包，体积是volume，有n个物体，编号为0,1,2,…n-1,对应的体积（cost ）和价值（weight）分别为cost[i]和weight[i],假定认为我们的最终目的是是背包的 重量最重 这一块怎么想也想不明白，看看dd，Matrix67,刘末鹏，xuyao，做有挑战性的事情才有 精彩的人生，而这才是自己想要的生活 正好，动态规划的题目先放一放，隔天再考虑hdu 2602也没有做正确