Advertisement
Guest User

Untitled

a guest
Feb 8th, 2016
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.58 KB | None | 0 0
  1. initialize的时候,initial第一行的时候要看多少列,第一列的时候要看多少行。
  2. 后面function正常。
  3. public class Solution {
  4. /**
  5. * @param obstacleGrid: A list of lists of integers
  6. * @return: An integer
  7. */
  8. public int uniquePathsWithObstacles(int[][] obstacleGrid) {
  9. // write your code here
  10. if (obstacleGrid == null || obstacleGrid.length == 0 ||
  11. obstacleGrid[0].length == 0 || obstacleGrid[0][0] == 1) {
  12. return 0;
  13. }
  14. int[][] state = new int[obstacleGrid.length][obstacleGrid[0].length];
  15.  
  16. //initialize
  17. for (int i = 0; i < obstacleGrid[0].length; i++) {
  18. if (i == 0) {
  19. state[0][i] = 1;
  20. } else if (obstacleGrid[0][i] == 1 || state[0][i - 1] == 0) {
  21. state[0][i] = 0;
  22. } else {
  23. state[0][i] = 1;
  24. }
  25. }
  26.  
  27. for (int i = 1; i < obstacleGrid.length; i++) {
  28. if (obstacleGrid[i][0] == 1 || state[i - 1][0] == 0) {
  29. state[i][0] = 0;
  30. } else {
  31. state[i][0] = 1;
  32. }
  33. }
  34.  
  35. for (int i = 1; i < obstacleGrid.length; i++) {
  36. for (int j = 1; j < obstacleGrid[0].length; j++) {
  37. if (obstacleGrid[i][j] == 1) {
  38. state[i][j] = 0;
  39. } else {
  40. state[i][j] = state[i - 1][j] + state[i][j - 1];
  41. }
  42. }
  43. }
  44.  
  45. return state[obstacleGrid.length - 1][obstacleGrid[0].length - 1];
  46. }
  47. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement