LeetCode 741. 체 리 따 기욕심 산법 편실패 하 다.

741. 앵두 를 따다
N x N 격자 하나 (grid) 앵두 밭 을 대표 하 는데 각 칸 은 다음 과 같은 세 가지 숫자의 하나 로 표시 된다.

0 은 이 칸 이 비어 있다 는 것 을 표시 하기 때문에 너 는 그것 을 입 을 수 있다.

1 이 칸 에 체 리 가 들 어 있다 는 뜻 이다. 체 리 를 따 서 입 어도 된다.

- 1 은 이 칸 에 가시덤불 이 있어 길 을 막 고 있다 는 뜻 이다.

당신 의 임 무 는 다음 규칙 을 준수 한 상태 에서 가능 한 한 많은 체 리 를 따 는 것 입 니 다.

위치 에서 (0, 0) 출발 하여 마지막 에 도착 (N - 1, N - 1) 하면 아래로 또는 오른쪽으로 만 갈 수 있 고 효과 적 인 칸 만 통과 할 수 있 습 니 다 (즉, 0 또는 1 의 칸 만 통과 할 수 있 습 니 다).

(N - 1, N - 1) 에 도착 하면 (0, 0) 으로 돌아 갈 때 까지 계속 가 야 합 니 다. 위로 또는 왼쪽으로 만 갈 수 있 고 효과 적 인 칸 만 통과 할 수 있 습 니 다.

한 칸 을 지나 고 이 칸 에 체 리 가 포함 되 어 있 을 때 체 리 를 따 고 이 칸 은 비어 있 습 니 다 (값 이 0 으로 변 합 니 다).

만약 (0, 0) 과 (N - 1, N - 1) 사이 에 지나 갈 수 있 는 경로 가 존재 하지 않 는 다 면 체 리 는 하나 도 떼 어 낼 수 없다.

예시 1:

  : grid =
[[0, 1, -1],
 [1, 0, -1],
 [1, 1,  1]]
  : 5
  ： 
   （0,0）   ，      ，   ，   ，   ，    (2, 2)。
      ，     4   ，     [[0,1,-1],[0,0,-1],[0,0,0]]。
  ，       ，   ，   ，   ，      ，    1   。
    ，     5   ，           。

설명:

grid  하나  N  *  N  의 2 차원 배열, N 의 수치 범 위 는 1 <= N <= 50 이다.

하나씩  grid[i][j]  집합  {-1, 0, 1} 그 중의 하나.

출발점 확보 가능  grid[0][0]  결승점  grid[N-1][N-1]  의 값 은 - 1 이 아니다.

version 01___DFS 옮 겨 다 니 기미 완성

public class Solution {
	/**
	 *        ;      ，                           
	 * 
	 * @param grid
	 * @return
	 */
	public int cherryPickup(int[][] grid) {
		//dfsGo dfsBack     1   ，       
		return dfsGo(grid, 0, 0) + dfsBack(grid, grid.length - 1, grid.length - 1);
	}
	
	//         ，        ，        ，
	//               ，              。
	int dfsGo(int[][] grid, int row, int column) {
		//     
		if (grid[row][column] == -1)
			return -1;

		//      
		if (row == grid.length - 1 || column == grid.length - 1) {
			if (row == grid.length - 1 && column == grid.length - 1)
				return grid[row][column];
			else if (column == grid.length - 1) {
				return dfsGo(grid, row + 1, column);}
			else
				return dfsGo(grid, row, column + 1);
		}

		//      
		int ds=dfsGo(grid,row+1,column);//ds___down step
		int rs=dfsGo(grid,row,column+1);//rs___right step
		if (ds>=rs&&ds==-1) return -1;//     ，   
		if(ds>=rs) {
			return ds+grid[row][column];
		}
		else {
			return rs+grid[row][column];
		}
			

	}
}

version2___동적 계획테스트 불 통과
        version 2 가 만난 테스트 사례: 마음 이 절망 적 이 야...
        1,1,1,1,0,0,0        0,0,0,1,0,0,0        0,0,0,1,0,0,1        1,0,0,1,0,0,0        0,0,0,1,0,0,0        0,0,0,1,0,0,0        0,0,0,1,1,1,1

public class Solution2 {

	/**
	 *              ，          ，              。
	 *       ，     grid[row][column],  grid[row][column]      
	 * nums[row][column]=max(nums[row-1][column],nums[row][column-1])+grid[row][column]
	 *               ，   nums  。
	 * 
	 * @param grid
	 * @return
	 */
	public int cherryPickup(int[][] grid) {
		// dfsGo dfsBack     1   ，       
		int go = go(grid);
		int back = back(grid);
		return (go + back)>0?go+back:0;
	}

	int go(int[][] grid) {
		//   nums           。
		int[][] nums = new int[grid.length][grid.length];
		getNums(nums, grid);
                //       。
		clearPath(nums, grid);

		return nums[grid.length - 1][grid.length - 1];
	}

	void getNums(int[][] nums, int[][] grid) {
		for (int i = 0; i < grid.length; i++)
			for (int j = 0; j < grid.length; j++) {
				//      
				if (grid[i][j] == -1)
					nums[i][j] = -1;
				else if (i > 0 && j > 0) {
					if (nums[i - 1][j] == -1 && nums[i][j - 1] == -1)
						nums[i][j] = -1;
					else
						nums[i][j] = grid[i][j] + (nums[i - 1][j] >= nums[i][j - 1] ? nums[i - 1][j] : nums[i][j - 1]);
				} else if (i == 0 && j > 0) {
					if (nums[i][j - 1] == -1)
						nums[i][j] = -1;
					else
						nums[i][j] = grid[i][j] + nums[i][j - 1];
				} else if (j == 0 && i > 0) {
					if (nums[i - 1][j] == -1)
						nums[i][j] = -1;
					else
						nums[i][j] = grid[i][j] + nums[i - 1][j];
				} else
					nums[0][0] = grid[0][0];
			}
	}

	void clearPath(int[][] nums, int[][] grid) {
		for (int i = grid.length - 1, j = grid.length-1;;) {
			grid[i][j] = 0;
			if (i > 0 && j > 0)
				if (nums[i - 1][j] >= nums[i][j - 1])
					i--;
				else
					j--;
			else if (i == 0 && j > 0)
				j--;
			else if (j == 0 && i > 0)
				i--;
			else
				break;
		}
	}

	int back(int[][] grid) {
		//   nums           。
		int[][] numsback = new int[grid.length][grid.length];
		getNumsBack(numsback, grid);
		return numsback[0][0];
	}
	void getNumsBack(int[][] nums, int[][] grid) {
		for (int i = grid.length-1; i>=0; i--)
			for (int j = grid.length-1; j >=0; j--) {
				//      
				if (grid[i][j] == -1)
					nums[i][j] = -1;
				else if (i < grid.length-1 && j < grid.length-1) {
					if (nums[i + 1][j] == -1 && nums[i][j + 1] == -1)
						nums[i][j] = -1;
					else
						nums[i][j] = grid[i][j] + (nums[i + 1][j] >= nums[i][j + 1] ? nums[i + 1][j] : nums[i][j + 1]);
				} else if (i == grid.length-1 && j != grid.length-1) {
					if (nums[i][j + 1] == -1)
						nums[i][j] = -1;
					else
						nums[i][j] = grid[i][j] + nums[i][j + 1];
				} else if (j == grid.length-1 && i != grid.length-1) {
					if (nums[i + 1][j] == -1)
						nums[i][j] = -1;
					else
						nums[i][j] = grid[i][j] + nums[i + 1][j];
				} else
					nums[grid.length-1][grid.length-1] = grid[grid.length-1][grid.length-1];
			}
	}

이로써 욕심 산법 은 목 표를 달성 하지 못 했다...