滑雪记忆化搜索解法

《滑雪记忆化搜索解法》由会员分享，可在线阅读，更多相关《滑雪记忆化搜索解法（6页珍藏版）》请在金锄头文库上搜索。

1、滑雪记忆化搜索解法滑雪记忆化搜索解法在给出这道题的解题报告之前，先看下记忆化搜索的个人理解。以最简单的递归求阶乘的函数进行说明。常见的求阶乘的代码是这样的：view plaincopy to clipboardprint?int fac(int n) if(n = 1) return 1; else return n * fac(n - 1); 为了实现不重复递归调用，使用一个全局数组对已求得的结果进行保存；另外，每次返回结果前，都对全局数组进行相应赋值。以下是实现代码：view plaincopy to clipboardprint?#include using namespace std;

2、 const int MAX = 20; /*全局数组。用来保存阶乘的结果。 *由于是全局数据，故不显式初始化的情况下， *所有数组元素元均被置为 0。 */ _int64 valArrMAX + 1; /*求阶乘函数。*/ _int64 fac(int n) /*对已求得 n!的情况下，则直接返回。避免了重复递归调用。*/ if(valArrn 0) return valArrn; /*以下代码跟平常求阶乘的代码很相似，只是多了对valArr 数组赋值的语句。*/ if(n = 1) valArrn = 1; return valArrn; valArrn = n * fac(n - 1);

3、 return valArrn; int main() /*若只是求 fac(MAX),则效率没有明显差异。 *但在循环过程中，实际上 fac(MAX)会调用 fac(MAX-1)的结果， *fac(MAX-1)会调用 fac(MAX-2)的结果故将已求得的结果保存起来， *效率就会得到提升。 */ for(int i = 1; i using namespace std; const int MAX_SIZE = 100; int r, c; int arrMAX_SIZEMAX_SIZE; /保存滑雪区域信息的全局数组。 int countMAX_SIZEMAX_SIZE; /保存每个点最

4、长滑雪长度信息的全局数组。 /*求点(i, j)最长滑雪长度的函数*/ int height(int i, int j) /*若已求得结果，则直接返回。*/ if(countij 0) return countij; /*保存(i, j)点的上下左右点的最大滑雪长度*/ int maxHeight = 0; /*由于要使用 arri - 1j，故先对 i-1 的合法性进判断*/ if(i - 1 = 0) /*只有(i-1, j)点的高度值小于(i, j)的点的高度值才进行计算*/ if(arri - 1j = 0) if(arrij - 1 =0，故被赋值后的 countij=1。 */ countij = maxHeight + 1; /*最后还返回(i, j)点的最大滑雪长度*/ return countij; int main() cin r c; /*初始化保存滑雪区域信息的数组*/ for(int i = 0; i arrij; int maxHeight = 0; int h; /*求得最长的“最长滑雪长度”*/ for(int i = 0; i maxHeight) maxHeight = h; cout maxHeight endl; return 0;