夺取宝藏问题（ipomy）oj算法设计与分析实践题目-爱代码爱编程
题目描述
思路分析
设Ipomy走到位置（i，j）所得到的价值之和为value（i，j），那么为了研究问题的方便我们不妨先研究其走到出口时的情况，即假设现在的状态是Ipomy已经走到了出口即处于位置（m-1，n-1），那么由于Ipomy只能向右走或者向下走，所以他的上一个状态要么是在（m-2，n-1）要么是在（m-1，n-2），而要让他走到（m-1，n-1）位置处获得最大价值，那么其走到上一步时获得的价值也应该是最大的，所以此问题又变成了问题规模减小了的求“获得最大价值”的问题，写到这儿，递归思想已经出来了。
程序源代码以及运行结果截图如下，在代码中给出了完整的注释
程序源代码
//夺取宝藏问题
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<malloc.h>
int max(int a, int b); //用于返回两个数中较大的一个；
int max_value(int **array, int m, int n);
int main()
{
int m, n,max_sum;
int** hide; //hide是一个二级指针，是指向指针的指针
while (scanf("%d%d", &m, &n) != EOF)
{
hide = (int**)malloc(sizeof(int*) * m);
for (int i = 0; i < m; i++)
{
hide[i] = (int*)malloc(sizeof(int) * n);
}//为二维数组动态申请内存
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
scanf("%d", &hide[i][j]);
}
}
max_sum = max_value(hide, m - 1, n - 1);
printf("%d\n", max_sum);
for (int i = 0; i < m; i++)
free(hide[i]);
free(hide);
}
return 0;
}
int max(int a, int b)
{
if (a >= b)
return a;
else
return b;
}
int max_value(int **array,int m, int n)
{
if (m == 1 && n == 0)
return array[1][0];
if (m == 0 && n == 1)
return array[0][1]; //递归出口即当其到达（0，1）位置或者（1，0）位置时即为递归出口。
if (m >= 2 && n == 0)
return max_value(array, m - 1, n) + array[m][n];
else if (m == 0 && n >= 2)
return max_value(array, m, n - 1) + array[m][n]; //这里需要说明的是，很显然当到达第一行或者第一列时没有办法继续对行或者列进行减一操作
else
{
return max(max_value(array, m - 1, n) + array[m][n], max_value(array, m, n - 1) + array[m][n]); //取两种路径中获得价值最大的一条路径
}
//算法思路，先考虑ipomy走到最后的出口的前一步是在哪里，由于只能向右或者向下，所以其前一格不是在(m-1,n)就是在(m,n-1)，
//若要价值之和最大,那么要求其从第一步到最后一步的前一步的价值之和也是最大的，所以就把问题拆分成了解法相同，问题规模不同的一些子问题，
//可用递归方法求解
}
运行结果截图
但是值得注意的是，由于此题二维数组的大小不确定，所以我们采用动态分配内存的方法，比直接将其定义为一个很大的数组hide[1000][1000]要好的多，直接将其定义为很大的数组会造成空间的浪费，而且需要内存中有那么多连续的存储空间才能申请成功。
动态内存分配的方法，可以先为二维数组的第一维申请内存空间，再分别为每一维申请内存空间
代码如下
hide = (int**)malloc(sizeof(int*) * m); //即先为第一维申请内存空间第一维即二维数组的行，二维数组的行本身是一个一维数组，而一维数组名是指向数组中第一个元素的地址，所以此时返回的是一个二级指针，即指向指针的指针。
for (int i = 0; i < m; i++)
{
hide[i] = (int*)malloc(sizeof(int) * n);
}//为二维数组动态申请内存