| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 402 人关注过本帖
标题:求教,最基础的动态规划的题目。
只看楼主 加入收藏
huicpc0876
Rank: 2
等 级:论坛游民
帖 子:69
专家分:50
注 册:2009-7-24
结帖率:92.59%
收藏
已结贴  问题点数:20 回复次数:2 
求教,最基础的动态规划的题目。
题目:序列中最长递增子序列长度。
    第一行输入要测试数据个数n

Sample Input
7
1 7 3 5 9 4 8
 
Sample Output
4

算法是,从最后一个开始,找到前面比他小的书,返回以前面这些数结尾的最长递增子序列的长度+1.
因为本人递归用的不好,想请高人写个代码参考下。
搜索更多相关主题的帖子: 动态规划 基础 
2009-07-30 00:10
NoSoul
Rank: 9Rank: 9Rank: 9
来 自:沈阳化工大学
等 级:蜘蛛侠
帖 子:283
专家分:1010
注 册:2009-6-6
收藏
得分:20 
回复 楼主 huicpc0876
#include<stdio.h>
int b[1010];
int amaxlen[1010];
int main()
{
    int n,i,j,nt,nMAX;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&b[i]);
    amaxlen[1]=1;
    for(i=2;i<=n;i++){
        nt=0;
        for(j=1;j<i;j++){
            if(b[i]>b[j]){
                if(nt<amaxlen[j])
                    nt=amaxlen[j];
            }
        }
        amaxlen[i]=nt+1;
    }
    nMAX=-1;
    for(i=1;i<=n;i++)
        if(nMAX<amaxlen[i])nMAX=amaxlen[i];
    printf("%d \n",nMAX);
    return 0;
}

[[it] 本帖最后由 NoSoul 于 2009-7-30 08:40 编辑 [/it]]

我想伸手拉近點,竟觸不到那邊,就欠一點點,但這一點點...卻好遠
2009-07-30 08:38
Mo诫
Rank: 4
等 级:业余侠客
帖 子:80
专家分:223
注 册:2009-7-29
收藏
得分:0 
主要用到冒泡排序
2009-07-30 09:06
快速回复:求教,最基础的动态规划的题目。
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.016262 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved