动态规划--最长上升子序列(Longest increasing subsequence)
前面写了最长公共子序列的问题。然后再加上自身对动态规划的理解，真到简单的DP问题很快就解决了。其实只要理解了动态规划的本质，那么再有针对性的去做这方的题目，思路很快就会有了。不错不错~加油
题目描述：POJ2533
给出一个数列，找出这个数列中最长上升子序列中所包含的个数。
解题思路：
DP问题解题的一般方法就是自下而上，即先求解小的问题，然后再根据小的问题来解决大的问题，最后得到解。但是这里还要满足的条件是最优子结构，即最优解包含着其子问题的最优解。
那么我们首先用arr[]数组(从0下标开始)存储要求的数列，用longest_num[i]数组来记录以i为结尾的子序列里面包含的最长上升子序列的数字个数。然后用循环控制，从下标为1开始求longest_num，并且记录找到的最大值，即可得到解。在我的程序里面，我还加了一个功能就是把最长上升子序列打印出来，如果存在有多个的话，那么就只打印最后一个。
最后根据下面的DP方程就可以进行求解了:
longest_num[i] = max{longest_num[j] + 1,longest_num[i]} 其中j < i && arr[j] < arr[i]
程序：
#include <stdio.h> #define MAX_N 1001 int arr[MAX_N]; int longest_num[MAX_N]; int bt[MAX_N]; int max_point = 0; int LIS(int n) { int max = 1; //最长上升子序列的个数 int i,j; for (i = 0; i < n; i++) //i下标之前(包括i)的最长上升子序列的个数 { longest_num[i] = 1; } for (i = 0; i < n; i++) //用于回溯 { bt[i] = -1; } for (i = 1; i < n; i++) { for (j = 0; j < i; j++) { if (arr[i] > arr[j] && longest_num[i] < longest_num[j] + 1) { longest_num[i] = longest_num[j] + 1; if (longest_num[i] >= max) { max = longest_num[i]; max_point = i; bt[i] = j; } } } } return max; } void backtrack(int point) { if (-1 == bt[point]) { printf("%d ",arr[point]); return; } else { backtrack(bt[point]); printf("%d ",arr[point]); } } int main() { int n,i,ret; FILE *fp; fp = fopen("in.txt","r"); if (fp == NULL) { printf("fopen error! "); return -1; } fscanf(fp,"%d",&n); for (i = 0; i < n; i++) { fscanf(fp,"%d",&arr[i]); } ret = LIS(n); printf("%d ",ret); backtrack(max_point); printf(" "); return 0; }
2013/8/16 16:21
测试数据：
7 1 7 3 5 9 4 8
测试结果：