Java DP, Prefix Sum, 2 & 5 factor nums
If we directly count the product of a path, we are very likely to get integer overflow.\nThe trailing zeros equals on the larger number of factors of 2 and 5 in
If we directly count the product of a path, we are very likely to get integer overflow.\n**The trailing zeros equals on the larger number of factors of 2 and 5 in the product.**\nWe need to count the four kinds of cornered paths.\n1. left-up\n2. up-right\n3. right-down\n4. down-left\n\nTo count the paths efficiently, we need to first compute the prefix sums of factor 2 and factor 5, from 4 directions.\n\nTime: O(mn)\nSpace: O(mn)\n\n```\nclass Solution {\n    public int maxTrailingZeros(int[][] grid) {\n        int m = grid.length;\n        int n = grid[0].length;\n        int[][] two = new int[m][n];\n        int[][] five = new int[m][n];\n        for (int i = 0; i < m; ++i) {\n            for (int j = 0; j < n; ++j) {\n                two[i][j] = getFactorNum(grid[i][j], 2);\n                five[i][j] = getFactorNum(grid[i][j], 5);\n            }\n        }\n        \n        int[][] left2 = new int[m][n];\n        int[][] left5 = new int[m][n];\n        for (int i = 0; i < m; ++i) {\n            int sum2 = 0;\n            int sum5 = 0;\n            for (int j = 0; j < n; ++j) {\n                sum2 += two[i][j];\n                sum5 += five[i][j];\n                left2[i][j] = sum2;\n                left5[i][j] = sum5;\n            }\n        }\n        \n        int[][] right2 = new int[m][n];\n        int[][] right5 = new int[m][n];\n        for (int i = 0; i < m; ++i) {\n            int sum2 = 0;\n            int sum5 = 0;\n            for (int j = n - 1; j >= 0; --j) {\n                sum2 += two[i][j];\n                sum5 += five[i][j];\n                right2[i][j] = sum2;\n                right5[i][j] = sum5;\n            }\n        }\n        \n        int[][] up2 = new int[m][n];\n        int[][] up5 = new int[m][n];\n        for (int j = 0; j < n; ++j) {\n            int sum2 = 0;\n            int sum5 = 0;\n            for (int i = 0; i < m; ++i) {\n                sum2 += two[i][j];\n                sum5 += five[i][j];\n                up2[i][j] = sum2;\n                up5[i][j] = sum5;\n            }\n        }\n        \n        int[][] down2 = new int[m][n];\n        int[][] down5 = new int[m][n];\n        for (int j = 0; j < n; ++j) {\n            int sum2 = 0;\n            int sum5 = 0;\n            for (int i = m - 1; i >= 0; --i) {\n                sum2 += two[i][j];\n                sum5 += five[i][j];\n                down2[i][j] = sum2;\n                down5[i][j] = sum5;\n            }\n        }\n        \n        int res = 0;\n        for (int i = 0; i < m; ++i) {\n            for (int j = 0; j < n; ++j) {\n                // left-up\n                if (i != 0 || j != 0) {\n                    int cur = Math.min(left2[i][j] + up2[i][j] - two[i][j], left5[i][j] + up5[i][j] - five[i][j]);\n                    res = Math.max(res, cur);\n                }\n                \n                // up-right\n                if (i != 0 || j != n - 1) {\n                    int cur = Math.min(right2[i][j] + up2[i][j] - two[i][j], right5[i][j] + up5[i][j] - five[i][j]);\n                    res = Math.max(res, cur);\n                }\n                \n                // right-down\n                if (i != m - 1 || j != n - 1) {\n                    int cur = Math.min(right2[i][j] + down2[i][j] - two[i][j], right5[i][j] + down5[i][j] - five[i][j]);\n                    res = Math.max(res, cur);\n                }\n                \n                // down-left\n                if (i != m - 1 || j != 0) {\n                    int cur = Math.min(left2[i][j] + down2[i][j] - two[i][j], left5[i][j] + down5[i][j] - five[i][j]);\n                    res = Math.max(res, cur);\n                }\n            }\n        }\n        return res;\n    }\n    \n    private int getFactorNum(int input, int factor) {\n        int res = 0;\n        while (input != 0 && input % factor == 0) {\n            ++res;\n            input /= factor;\n        }\n        return res;\n    }\n}\n```
['Dynamic Programming', 'Prefix Sum', 'Java']