一个n*n的方格，每个格子中间有一个数字是2或者5，现在从方格的左上角走到右下角，每次只能选择向下或者向右移动一格两种移动方式，让所有经过的格子中的数字相乘，求使最后的结果中末尾处0的数字最少。
一个n*n的方格，每个格子中间有一个数字是2或者5，现在从方格的左上角走到右下角，每次只能选择向下或者向右移动一格两种移动方式，让所有经过的格子中的数字相乘，求使最后的结果中末尾处0的数字最少。
第一行是一个正整数n(0<n<100)。
接下来n行是一个n*n的矩阵。
一个正整数m，表示最后的结果末尾处最少有x个0。
4
2 5 2 5
5 2 5 2
2 5 5 5
2 2 2 2
1
解题思路：
本题的状态转移不同于普通的递推，因为要求的是相乘后末尾0的数量最少，用搜索剪枝的方法看似可解，但因刚说的原因，在实现的过程中会有很多麻烦，很容易超时，所以还是考虑动态规划解法。
首先，由乘法结合律，末尾0的数量可由序列中2和5配对的数量得出，有一对2，5相乘，即有一个末尾0.
接下来这里有一个关键点，即：按题目要求从左上走到右下，所经过的格子总数一定是S=2×n-1个！
这一点很关键，想到这一点之后本题基本就可以写dp了，可惜不是自己想到的，多亏学弟的提醒
这样一来，2和5的总数就知道了，那么只要分别统计2和5能达到的最大数量（暂设为M2和M5），即可算出对与这两种情况最后分别会有多少末尾0
例如：
以样例数据为例，n=4,S=2*n-1=7
M2=6，M5=4
对于M2，该情况下有6个2，即有1个5，末尾0数即为1；
对于M5，该情况下有4个5，即有3个2，末尾0数即为3；
两相比较，得出最终答案应为1.
Ps：注意不能只统计2或5，例如对样例数据，如果只统计5的话，就无法得出最优解了
代码：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int map[105][105],dp2[105][105],dp5[105][105];
int main()
{
int n;
while(cin>>n)
{
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
scanf("%d",&map[i][j]);
}
}
memset(dp2,0,sizeof(dp2));
memset(dp5,0,sizeof(dp5));
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
dp2[i][j]=max(dp2[i-1][j],dp2[i][j-1]);
if(map[i][j]==2) ++dp2[i][j];
dp5[i][j]=max(dp5[i-1][j],dp5[i][j-1]);
if(map[i][j]==5) ++dp5[i][j];
}
}
int ans=max(dp2[n][n],dp5[n][n]);
if(ans*2>(2*n-1)) ans=2*n-1-ans;
cout<<ans<<endl;
}
return 0;
}zzuli1430 多少个0 （dp递推,布布扣,bubuko.com
原文：http://blog.csdn.net/harrypoirot/article/details/24346749