http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1231
直接递推。
在保存最大值的时候同时保存有多少条到达最大值的路径，注意第一行第一列的情况即可。
别忘了 取模。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
const int maxn = ;
int dp[maxn][maxn],p[maxn][maxn],q[maxn][maxn];
int main()
{
int n;
while(~scanf("%d",&n))
{
memset(dp,,sizeof(dp));
for(int i=;i<=n;i++) {
for(int j=;j<=n;j++) {
scanf("%d",&p[i][j]);
q[i][j]=;
}
}
for(int i=;i<=n;i++) {
for(int j=;j<=n;j++) {
if(dp[i-][j]>dp[i][j-]) {
dp[i][j]=dp[i-][j]+p[i][j];
if(i==||j==) continue;
q[i][j]=q[i-][j];
}
else if(dp[i][j-]>dp[i-][j]) {
dp[i][j]=dp[i][j-]+p[i][j];
if(i==||j==) continue;
q[i][j]=q[i][j-];
}
else {
dp[i][j]=dp[i-][j]+p[i][j];
if(i==||j==) continue;
q[i][j]=q[i-][j]+q[i][j-];
}
q[i][j]%=;
}
}
// for(int i=1;i<=n;i++) {
// for(int j=1;j<=n;j++)
// printf("%d ",q[i][j]);
// printf("\n");
//}
printf("%d\n",q[n][n]%);
}
return ;
}