알고리즘 매일 세 문제 -- 동적 계획

1. 최 장 괄호
[제목 설명] '(' 와 ')' 만 포함 하 는 문자열 을 지정 하고 가장 긴 괄호 를 포함 하 는 하위 문자열 의 길 이 를 찾 습 니 다.
[예제 입력]
        " )()()) "
[출력 예시]
        4 
[문제 풀이 아이디어!]
1. 문자열 을 옮 겨 다 니 며,
       '(' 를 만나면 '(' 에 대응 하 는 위 치 를 창고 에 넣 습 니 다.
       ')' 를 만 나 고 스 택 이 비어 있 지 않 으 면 len 배열 에서 ')' 의 위치 와 대응 하 는 '(' 의 위 치 를 1 로 표시 하고 스 택 을 나 갑 니 다.
2. 태그 배열 을 옮 겨 다 니 며 연속 으로 표 시 된 최대 길이, 즉 가장 긴 유효 괄호 를 얻 을 수 있 습 니 다.

public int longestValidParentheses(String s) {
        int n = s.length();
        //    ‘（’    
        ArrayList l = new ArrayList();
        //  ‘（’ ‘）’，       ，   1
        int[] len = new int[n];
        int res = 0;
        
        //     ，     ‘（’ ‘）’
        for(int i = 0; i < s.length(); i++) {
        	if(s.charAt(i) == '(')
        		l.add(i);//  
        	if(s.charAt(i) == ')' && l.size() > 0) { //       （），     1
        		len[i] = 1;
        		len[l.get(l.size()-1)] = 1;
        		l.remove(l.size()-1);//  
        	}
        }
	
	//      ，         
        for(int i = 0; i < n; i++) {
        	if(len[i] == 0)
        		continue;
        	int tmp = 0;
        	while(i < n && len[i] > 0)
        		tmp += len[i++];
        	if(tmp > res)
        		res = tmp;
        }
        
		return res;
    }

2. 다른 경로 II
[제목 설명] 한 로봇 은 m x n 격자 의 왼쪽 상단 에 있 습 니 다. (시작 점 은 아래 그림 에서 "Start" 로 표 시 됩 니 다.) 로봇 은 매번 아래로 또는 오른쪽으로 한 걸음 만 이동 할 수 있 습 니 다. 로봇 은 격자 의 오른쪽 하단 에 도달 하려 고 합 니 다. (아래 그림 에서 "Finish" 로 표 시 됩 니 다)... 지금 은 격자 에 장애물 이 있 는 것 을 고려 하고 있 습 니 다. 그러면 왼쪽 상단 에서 오른쪽 하단 까지 몇 개의 서로 다른 경로 가 있 습 니까?
[예제 입력]
        [   [0,0,0],   [0,1,0],   [0,0,0] ]
[출력 예시]
       2
[문제 풀이 아이디어!]
장애물 이 있 는 위치, 경로 개수 = 0, 장애물 이 왼쪽 상단 에 있 으 면 오른쪽 하단 에 도달 할 수 없습니다.
장애물 이 없 는 위치:
           첫 번 째 열 (위) 과 첫 번 째 줄 (왼쪽) 을 제외 하고 다른 좌표 에 도착 하 는 경 로 는 두 가지 가 있 습 니 다. 왼쪽 과 위,
           따라서 다른 좌표 의 경로 개수 = 왼쪽 좌표 의 경로 개수 + 위쪽 좌표 의 경로 개수.

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if(obstacleGrid.length <= 0 || obstacleGrid[0][0] == 1)
        	return 0;
        int r = obstacleGrid.length;
        int c = obstacleGrid[0].length;
        int[][] steps = new int[r][c];

        for(int i = 0; i < r; i++) {
        	for(int j = 0; j < c; j++) {
        		if(obstacleGrid[i][j] == 0) { //      
        			if(i == 0 && j == 0) //     
        				steps[i][j] = 1;
	        		if(i == 0 && j > 0) //    
	        			steps[i][j] = steps[i][j-1];
	        		if(j == 0 && i > 0) //   
	        			steps[i][j] = steps[i-1][j];
	        		if(i > 0 && j > 0)
	        			steps[i][j] = steps[i-1][j] + steps[i][j-1];
        		}
        	}
        }
        return steps[r-1][c-1];

 
3. 최소 경로 와
[제목 설명] 마이너스 정 수 를 포함 하지 않 는 mxn 격자 를 지정 합 니 다. 왼쪽 상단 에서 오른쪽 하단 까지 의 경 로 를 찾 아 경로 의 숫자 합 계 를 최소 화 하 십시오.
[설명] 매번 아래로 또는 오른쪽으로 한 걸음 만 이동 할 수 있 습 니 다.
[예제 입력]
          [   [1,3,1], [1,5,1], [4,2,1] ]
[출력 예시]
          7
[문제 풀이 아이디어!]
첫 번 째 열 (위쪽) 과 첫 번 째 줄 (왼쪽) 을 제외 하고 다른 좌표 에 도착 하 는 최소 경로 와 = 다른 좌표 + min (왼쪽 좌표, 위쪽 좌표);

public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] sum = grid.clone();
        for(int i = 0; i < grid.length; i++)
        	for(int j = 0; j < grid[i].length; j++) {
        		if(i == 0 && j > 0)
        			sum[i][j] += sum[i][j-1];
        		if(j == 0 && i > 0)
        			sum[i][j] += sum[i-1][j];
        		if(i > 0 && j > 0)
        			sum[i][j] += Math.min(sum[i-1][j], sum[i][j-1]);
        	}
        return sum[m-1][n-1];
    }