原创
问题描述：
求出数组arr的最长递增子序列长度；
比如：arr={5,64,8,1,55,99,101}；的最长递增子序列长度为5
解题思路：
此题属于动态分配类的题目，求解当前问题，可以先求解它的子问题，子问题不断堆叠最终求得答案。
我们先抽象出动态规划数组dp，dp[i]代表数组截止到arr[i]这个元素时能找到的最长递增子序列。
要求dp[i]，我们只需要把这个“尾巴”接到前面它能接上去的元素尾部就行了，但是我们从“前面”
所有尾部中选出dp值最大的接上去，这样才能保证dp[i]表示这个位置的最长递增子序列。
比如，上面序列的99，可以接到5,64,8,1,55后面，但是只有接到55后面，dp[5]（下标从0开始）
才能表示最大递增子序列长度。所以，我们需要从前面的所有dp值中选出最大的，假设为dp[j]，
如果满足arr[i]>arr[j]，接上去。但是如果arr[i]是arr[0]~arr[i]中的最小元素，dp[i]的值只能是1了。
代码：
1 #include<stdio.h> 2 #include<stdlib.h> 3 4 int main() 5 { 6 int n; 7 scanf("%d",&n); 8 int i; 9 int *arr; 10 arr=(int *)malloc(sizeof(int)*n); 11 int *dp=(int *)malloc(sizeof(int)*n); //动态规划表 12 for(i=0;i<=n-1;i++) 13 scanf("%d",&arr[i]); 14 15 dp[0]=1; 16 int j; 17 for(i=0;i<=n-1;i++) 18 { 19 int max=0; 20 for(j=0;j<=i-1;j++) 21 { 22 if(arr[i]>arr[j] && dp[j]>max) 23 max=dp[j]; 24 dp[i]=max+1; 25 } 26 } 27 28 int max; 29 max=dp[0]; 30 for(i=1;i<=n-1;i++) 31 if(dp[i]>max) 32 max=dp[i]; 33 printf("%d",max); 34 return 0; 35 }
2018-03-20
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
