[前缀和]leetcode2245：转角路径的乘积中最多能有几个尾随零(medium)

题目：

题解：

思路：一维前缀和+枚举

代码如下：

class Solution {
public:
    // 乘积尾随0的数量是所有乘数中因子2数量之和与因子5数量之和中的较小值
    // 在做乘积的过程中，尾随0的数量只会增加不会减少，因此我们应该让尽量多的数参与乘积运算，这就说最有路径一定是从某个边界出发拐个弯在走到另外一个边界
    int maxTrailingZeros(vector>& grid) {
        int n=grid.size(),m=grid[0].size();
        // 创建四个前缀和数组，统计g[i][j]左边、上边的因子2 5的个数
        vector> f2(n+1),g2(n+1),f5(n+1),g5(n+1);
        for(int i=0;i<=n;++i)f2[i]=g2[i]=f5[i]=g5[i]=vector (m+1,0);
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j)
            {
                int x=grid[i-1][j-1];
                int two=0,five=0;
                while(x%2==0)two++,x/=2;
                while(x%5==0)five++,x/=5;
                f2[i][j]=f2[i][j-1]+two,f5[i][j]=f5[i][j-1]+five;// 左边
                g2[i][j]=g2[i-1][j]+two,g5[i][j]=g5[i-1][j]+five;// 上边
            }

        // 枚举拐点(i,j)，然后计算4个方向的最大值即可
        // 乘积尾随0的数量是所有乘数中因子2数量之和与因子5数量之和中的较小值
        int res=0;
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j)
            {
                // 从左边向右边出发，然后向上走
                res=max(res,min(f2[i][j]+g2[i-1][j],f5[i][j]+g5[i-1][j]));
                // 从左边向右边出发，然后向下走
                res=max(res,min(f2[i][j]+g2[n][j]-g2[i][j],f5[i][j]+g5[n][j]-g5[i][j]));
                // 从右边向左边出发，然后向上走
                res=max(res,min(f2[i][m]-f2[i][j]+g2[i][j],f5[i][m]-f5[i][j]+g5[i][j]));
                // 从右边向左边出发，然后向下走
                res=max(res,min(f2[i][m]-f2[i][j]+g2[n][j]-g2[i-1][j],f5[i][m]-f5[i][j]+g5[n][j]-g5[i-1][j]));
            }
        return res;
    }
};