poj 1088 滑雪

题意:找出最长的递增道路,可以上下左右四个方向走

DP方程:step[ i ][ j ] = max{ step[ i-1][ j ],  step[ i ][ j-1],  step[ i+1][ j ],  step[ i ][ j+1] };

 借鉴各类大牛的代码,终于写出来了第一道记忆化搜索

#include<stdio.h>
//全局变量自动赋0 
int mp[101][101];//记录原始数据
int step[101][101];//记录每个地方的最大滑雪步数
int N,M;

int DP(int row,int column)//行列不要用x,y
{
	int max=0;
	if(step[row][column]>0)  return step[row][column];//已经遍历过了 就不要在进行了
	//找上下左右四个方向中step最大的然后加到该位置中
	//上
	if (row-1>=0 && mp[row-1][column]<mp[row][column])
	{
		if(max<DP(row-1,column))
			max=DP(row-1,column);
	}
    //下
	if(row+1<N && mp[row+1][column]<mp[row][column])
	{
		if(max<DP(row+1,column))
			max=DP(row+1,column);
	}
	//左
	if(column-1>=0 && mp[row][column-1]<mp[row][column])
	{
		if(max<DP(row,column-1))
			max=DP(row,column-1);
	}
	//右
	if(column+1<M && mp[row][column+1]<mp[row][column])
	{
		if(max<DP(row,column+1))
			max=DP(row,column+1);
	}
	max++;//算上自己本身那一步 
	//return的东西非常重要;
	//1-2-3-4这四个点从4开始
	//找的话会把1,2,3都记录了
	return step[row][column]=max;
}

int main()
{	
	int i,j;
	scanf("%d%d",&N,&M);
	for (i=0;i<N;i++)
		for(j=0;j<M;j++)
		{
			scanf("%d",&mp[i][j]);
			step[i][j]=0;
		}
		for (i=0;i<N;i++)
			for (j=0;j<M;j++)
				DP(i,j);
			//step[i][j]=DP(i,j)这样会超时
			//如果从4开始找就只会把4的结果记录
			//1,2,3没有记录
		int max=0;
		for (i=0;i<N;i++)
		for (j=0;j<M;j++)
			if(max<step[i][j])  max=step[i][j];
		printf("%d\n",max);
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器之心

人生苦短,为什么我要用Python?

本教程的目的是让你相信两件事:首先,Python 是一种非常棒的编程语言;其次,如果你是一名科学家,Python 很可能值得你去学习。本教程并非想要说明 Pyt...

1041
来自专栏嵌入式程序猿

宏函数使用的陷阱

在嵌入式软件设计中,有工程师经常会定义一些宏函数,宏函数的使用虽然可以减少开销,但是宏函数的使用一定要小心,例如我们定义一个求取两个数中的较大者的宏函数来做试验...

3559
来自专栏大数据风控

懒癌必备-dplyr和data.table让你的数据分析事半功倍

duang,duang!Erin又上线为大家分享干货来了。 最近Erin在做信用风险评级模型的开发,几千行的代码敲的我头晕眼花。作为一个懒癌晚期,并且追求高...

2197
来自专栏数据和云

大象起舞:用PostgreSQL解海盗分金问题

今天午休期间刷微信,看到云和恩墨的盖总转了一条朋友圈,说杨长老在Oracle中用SQL解海盗分金问题(原文《无往不利:用SQL解海盗分金的利益最大化问题》,看完...

1316
来自专栏牛客网

头条后端三面

先说了一个解法,结果一想再加面试官提醒,有点问题。突然想起了分治,但是合并的步骤和复杂度有点记不清了。面试官提了按增量为K的划分网格的做法,手写,写完结束

2004
来自专栏数据小魔方

空间数据可视化笔记——simple features空间对象基础

是不是感觉被封面图和不明觉厉的题目给骗进来了哈哈哈,今天这篇是理论篇,没有多少案例,而且还很长,所以静不下心的小伙伴儿可以先收藏着,时间充裕了再看。 ---- ...

3325
来自专栏深度学习计算机视觉

迪米特法则

一个对象应该对其他对象有最少的了解 迪米特法则对低耦合提出了明确的要求 1、只和朋友交流 虽然一个类和多个类产生依赖关系,但它只和朋友类交流 朋友类的定义...

3588
来自专栏CSDN技术头条

关系型数据库是如何运作的(上)

一说到关系型数据库,我总感觉缺了点什么。如果你尝试透过“关系型数据库是如何运作的”的关键词句来进行搜索,其搜索结果是少量的而且内容是简短的。难道说是由于它已经太...

2138
来自专栏机器学习和数学

[编程经验] Pandas中比较好用的几个方法

话说我现在好久不做深度学习的东西了,做了一段时间是的NLP,以为可以去尝试各种高大上的算法,然而现在还并没有,反而觉得更像是做数据挖掘的。。平时遇到的比较多的问...

3495
来自专栏云飞学编程

稳固基础!一节课掌握python内置数据类型—列表

点击链接加入群【python┮】:https://jq.qq.com/?_wv=1027&k=577hmAB

872

扫码关注云+社区

领取腾讯云代金券