Java|| easy to understand || dp || 100% time and memory
HINT1:\nif we want to get the number of trailing zeros, we only need to figure out how many 5 and 2 the product has.\n\nHINT2:\nFor each element as a corner, we
HINT1:\nif we want to get the number of trailing zeros, we only need to figure out how many 5 and 2 the product has.\n\nHINT2:\nFor each element as a corner, we have 4 directions and we need to combine any of the 2 to get a valid path.  So every corner has 6 different paths.\n\n\n1.\n0 1 0 0 \n0 1 0 0\n0 1 0 0\n0 1 0 0\n\n2.\n0 1 0 0 \n0 1 1 1\n0 0 0 0\n0 0 0 0\n\n3.\n0 1 0 0 \n1 1 0 0\n0 0 0 0\n0 0 0 0\n\n4.\n0 0 0 0 \n1 1 1 1\n0 0 0 0\n0 0 0 0\n\n5.\n0 0 0 0 \n1 1 0 0\n0 1 0 0\n0 1 0 0\n\n6.\n0 0 0 0 \n0 1 1 1\n0 1 0 0\n0 1 0 0\n\n\n\n```\n \n public static int maxTrailingZeros(int[][] grid) {\n        /*calculate how many 5 and 2 grid[i][j] has\n        int[][] five = new int[grid.length][grid[0].length];\n        int[][] two = new int[grid.length][grid[0].length];\n        for (int i = 0; i < grid.length; i++) {\n            for (int j = 0; j < grid[0].length; j++) {\n                int origin = grid[i][j];\n                while (origin % 5 == 0 && origin != 0) {\n                    five[i][j] += 1;\n                    origin = origin / 5;\n                }\n                origin = grid[i][j];\n                while (origin % 2 == 0 && origin != 0) {\n                    two[i][j] += 1;\n                    origin = origin / 2;\n                }\n            }\n        }\n        // use four dp array to save the sum of 5 and 2 in two directions\n        int[][] dp51 = new int[grid.length][grid[0].length];\n        int[][] dp21 = new int[grid.length][grid[0].length];\n        int[][] dp52 = new int[grid.length][grid[0].length];\n        int[][] dp22 = new int[grid.length][grid[0].length];\n\n        for (int i = 0; i < grid.length; i++) {\n            for (int j = 0; j < grid[0].length; j++) {\n                if (i == 0) {\n                    dp51[i][j] = five[i][j];\n                    dp21[i][j] = two[i][j];\n                } else {\n                    dp51[i][j] = dp51[i - 1][j] + five[i][j];\n                    dp21[i][j] = dp21[i - 1][j] + two[i][j];\n                }\n                if (j == 0) {\n                    dp52[i][j] = five[i][j];\n                    dp22[i][j] = two[i][j];\n                } else {\n                    dp52[i][j] = dp52[i][j - 1] + five[i][j];\n                    dp22[i][j] = dp22[i][j - 1] + two[i][j];\n                }\n            }\n        }\n        \n        //we have 4 choices and combine any of 2\n        int max = 0;\n        for (int i = 0; i < grid.length; i++) {\n            for (int j = 0; j < grid[0].length; j++) {\n                int fiveNum = dp51[i][j];\n                int twoNum = dp21[i][j];\n\n                int fiveNum2 = dp52[i][j];\n                int twoNum2 = dp22[i][j];\n\n                int fiveNum1 = dp51[grid.length - 1][j] - dp51[i][j] + five[i][j];\n                int twoNum1 = dp21[grid.length - 1][j] - dp21[i][j] + two[i][j];\n\n                int fiveNum3 = dp52[i][grid[0].length - 1] - dp52[i][j] + five[i][j];\n                int twoNum3 = dp22[i][grid[0].length - 1] - dp22[i][j] + two[i][j];\n\n\n                max = Math.max(max, Math.min(fiveNum + fiveNum1 - five[i][j], twoNum + twoNum1 - two[i][j]));\n                max = Math.max(max, Math.min(fiveNum + fiveNum2 - five[i][j], twoNum + twoNum2 - two[i][j]));\n                max = Math.max(max, Math.min(fiveNum + fiveNum3 - five[i][j], twoNum + twoNum3 - two[i][j]));\n                max = Math.max(max, Math.min(fiveNum2 + fiveNum1 - five[i][j], twoNum2 + twoNum1 - two[i][j]));\n                max = Math.max(max, Math.min(fiveNum3 + fiveNum1 - five[i][j], twoNum3 + twoNum1 - two[i][j]));\n                max = Math.max(max, Math.min(fiveNum2 + fiveNum3 - five[i][j], twoNum2 + twoNum3 - two[i][j]));\n            }\n        }\n        return max;\n    }\n \n \n  ```\n \n \n \n
['Dynamic Programming', 'Java']