We have as an input a grid of cells with numbers. The numbers can be 0, positive or negative. To move across a cell, we must have positive points, meaning greater than 0 points. When we move to a new cell, we add that amount to out total points. We can only move from one cell to the right or down.
Input: int[][] points = {{-4, -8, 10}, {-5, -10, 2}, {10, 30, -7}}; Output: 10 Explanation: The initial minimum points to reach destination are 10 because we start from -4, we go to -5 and this equals to -9. After this point we have positive, high numbers, so those 2 points must be covered in the beginning. In order to have a positive number in order to be able to keep going, we add one, so we need 10 initial points: one to have positive number and 9 to make up for the negative value. |
Solution:
1. static int minInitialPoints(int[][] points) { 2. int rows = points.length; 3. int columns = points[0].length; 4. int[][] minimumInitialPoints = new int[rows][columns]; 5. 6. minimumInitialPoints[rows - 1][columns - 1] = points[rows - 1][columns - 1] > 0 ? 1 : Math.abs(points[rows - 1][columns - 1]) + 1; 7. 8. for (int i = rows - 2; i >= 0; i--) { 9. minimumInitialPoints[i][columns - 1] = Math.max(minimumInitialPoints[i + 1][columns - 1] - points[i][columns - 1], 1); 10. } 11. for (int j = columns - 2; j >= 0; j--) { 12. minimumInitialPoints[rows - 1][j] = Math.max(minimumInitialPoints[rows - 1][j + 1] - points[rows - 1][j], 1); 13. } 14. 15. for (int i = rows - 2; i >= 0; i--) { 16. for (int j = columns - 2; j >= 0; j--) { 17. int minPoints = Math.min(minimumInitialPoints[i + 1][j], minimumInitialPoints[i][j + 1]); 18. minimumInitialPoints[i][j] = Math.max(minPoints - points[i][j], 1); 19. } 20. } 21. 22. return minimumInitialPoints[0][0]; 23. } 24.