在一个m行n列方格矩阵中，每一个方格内摆放着价值不等的宝贝（价值可正可负），让小明感到好奇的是，从左上角到达右下角的所有可能路线中，能捡到宝贝的价值总和最大是多少？而且这种达到最大值的路线
又有多少条？【注意：只能从一个格子向下或向右走到相邻格子，并且走到的格子宝贝一定会被捡起。】

输入格式:

第一行为整数m，n（均不大于100），下一行开始会有一个m行n列的整数方阵，对应方格矩阵中的宝贝价值（这些值的绝对值都不超过500）。

输出格式:

单独一行输出2个整数，分别为能捡到宝贝价值总和的最大值和达到最大值的路线数量，2个整数间隔一个空格。

输入样例:

在这里给出一组输入。例如：

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

输出样例:

对应的输出为：

26 3

 思路：

一个二维数组，map[i][j]表示从起点（0,0）到（i，j）的最大值
第一行和第一列只有一种可能，从上来或者从下来，所以初始化map和way里面的第一列和第一行
剩下的有两种可能，从上来或者从左来，比较两种情况，哪个价值更大

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int map[100][100];//直接在map上计算最大值了，不另外弄一个dp了
    int way[100][100];//记录路径，1为到这个点只有一条路
    int m;
    int n;
    cin>>m;
    cin>>n;//!!!又忘记输入了！！！！！！
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)//!!!!j<n
        {
            cin>>map[i][j];
        }
    }
    //初始化第一列
    for(int i=1;i<m;i++)//从1开始！！！！！越界了！！！
    {
        map[i][0]+=map[i-1][0];
        way[i][0]=1;
    }
    //初始化第一行
    for(int i=1;i<n;i++)
    {
        map[0][i]+=map[0][i-1];
        way[0][i]=1;
    }
    way[0][0]=1;
     for(int i=1;i<m;i++)
    {
        for(int j=1;j<n;j++)//j<n
        {
            if(map[i][j]+map[i][j-1]>map[i][j]+map[i-1][j])//左边最大
            {
                 map[i][j]+=map[i][j-1];
                 way[i][j]=way[i][j-1];//路线总数不变，从左来
            }
            if(map[i][j]+map[i][j-1]<map[i][j]+map[i-1][j])//上面最大
            {
                 map[i][j]+=map[i-1][j];
                 way[i][j]=way[i-1][j];//路线总数不变，从右来
            }
            if(map[i][j]+map[i][j-1]==map[i][j]+map[i-1][j])//一样大
            {
                 map[i][j]+=map[i-1][j];
                 way[i][j]=way[i][j-1]+way[i-1][j];//路线总数要加起来，左右都可以
            }
        }
    }
    cout<<map[m-1][n-1]<<" "<<way[m-1][n-1];
    return 0;
}