软件学院三天三班天梯模拟L5-2寻宝路线(第十十分)(动态规划深度优先搜索逆向推理记忆化技巧)

在一个由m行n列构成的方格矩阵中，每个单元格内均放置着价值各异的宝物（价值可为正数或负数）。小明对此产生了兴趣，他想知道在从左上角出发至右下角的所有可行路径中，能够收集到最大总价值的路径是哪一条？同时，这样的最优路径究竟存在多少条？【特别说明：移动过程中仅允许向右或向下相邻格子行进，且每经过一个格子，其中的宝物都将被采集。

输入格式:

第一行给出两个整数m和n（均不超过100），随后的m行中将依次输入n个整数，构成一个m行n列的矩阵，该矩阵中的每个元素代表对应方格内所蕴含的宝物价值（所有数值的绝对值均控制在500以内）。

输出格式:

输出两个整数，分别表示所能获取的宝物总价值的最大值以及实现该最大值的路径数目，两个数值之间以一个空格分隔。

输入样例解析

以下将提供一组示例输入内容。例如：

 4  5

    
 2  -1  6  -2  9
    
 -3  2  5  -5  1
    
 5   8  3  -2  4
    
 5   2  8  -4  7
    
    
    
    

输出样例:

对应的结果呈现如下：

    26 3
    

思路:

这是一个典型的动态规划问题，要求从网格的左上角出发，沿着只能向右或向下移动的路径抵达左下角，在经过每个格子