动态规划之滑雪问题c++实现

2013年8月22日 1点热度 0条评论 来源: 浪漫代码

问题描述:

      Michael喜欢滑雪百这并不奇怪, 因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael想知道在一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。要求找出最长的滑雪路径。下面是一个例子

 1 2  3  4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

      一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度减小。在上面的例子中,一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上,这是最长的一条。

 算法基本思想:

动态规划的实质是分治思想和解决冗余,因此,动态规划是一种将问题实例分解为更小的、相似的子问题,并存储子问题的解而避免计算重复的子问题,以解决最优化问题的算法策略。在求解过程中,该方法也是通过求解局部子问题的解达到全局最优解,但与分治法和贪心法不同的是, 动态规划允许这些子问题不独立,也允许其通过自身子问题的解作出选择,该方法对每一个子问题只解一次,并将结果保存 起来,避免每次碰到时都要重复计算。子问题的重叠性 动态规划算法的关键在于解决冗余,这是动态规划算法的根本目的。

#include <iostream>
using namespace std;

int a[100][100];
int b[100][100];

int line,row;

int skating(int i,int j)
{
   if(b[i][j]!=-1)
	   return b[i][j];
   int max=0;
   if(i>0&&a[i][j]>a[i-1][j]&&max<skating(i-1,j))
	   max=skating(i-1,j);
   if(i<line-1&&a[i][j]>a[i+1][j]&&max<skating(i+1,j))
	   max=skating(i+1,j);
   if(j>0&&a[i][j]>a[i][j-1]&&max<skating(i,j-1))
	   max=skating(i,j-1);
   if(j<row-1&&a[i][j]>a[i][j+1]&&max<skating(i,j+1))
	   max=skating(i,j+1);

   b[i][j]=max+1;
   return b[i][j];
}

int main()
{
    cin>>line>>row;
    for(int i=0;i<line;i++)
	   for(int j=0;j<row;j++)
		   cin>>a[i][j];
    for(int i=0;i<line;i++)
	   for(int j=0;j<row;j++)
		   b[i][j]=-1;
    for(int i=0;i<line;i++)
	   for(int j=0;j<row;j++)
	   {
	       b[i][j]=skating(i,j);
	   }
	int max=0;
    for(int i=0;i<line;i++)
	   for(int j=0;j<row;j++)
	      if(max<b[i][j]) max=b[i][j];
	cout<<max<<endl;
}

 

    原文作者:浪漫代码
    原文地址: https://blog.csdn.net/u010797915/article/details/10201579
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。