leetcode 퀴즈 요약, 동적 계획 I(Triangle, Unique Paths I/II, Minimum Path Sum, Climbing Stairs, Jump Game, Word Break)

주로 동적 기획의 앞의 두 종류, 수조와 서열이다.dp의 제목을 생각해야 한다. 예를 들어 1.최대 최소값 찾기 2.xxx가 가능합니까?3. 모든 실행 가능한 수량을 계산한다.
수조류에서 흔히 볼 수 있는 문제형은 가장 짧은 경로, 가능한 경로 수를 포함한다.
서열류는 흔히 볼 수 있는 문제형: 서로 다른 걸음으로 전진할 수 있는지, 도달할 수 있는지, 몇 가지 조합이다.서열의 다른 분할 방식.
해법: 1.분석 2.방정식으로 해석을 표시하면 보통 f(n)=min{f(n-1)+1, f(n-2)+1} 3.초기 값인 f(0)와 같은 저장 그룹을 만듭니다.4. 배열에 대해 순서대로 값을 계산한다.보통 그룹의 마지막 값인 f (s.length) 로 풀기
1. Triangle 문제는 삼각형 2차원 그룹으로 상하를 연결하는 최소 노드의 경로를 찾아낸다.전형적인 dp는 각 지점마다 두 개의 길이 도착하고 양쪽을 비교한 후에 귀속된다.첫 번째 분석은 아래에서 위로 계산하고 마지막 줄과 같은 큰 수조로 중간 결과를 저장하는 것이다.두 번째 단계는 공식을 씁니다. f(n)=value(n)+min{f(n), f(n+1)} 세 번째 단계는 코드를 씁니다. 첫 번째 그룹에 값을 부여한 다음에 순환으로 계속 위로 올라갑니다.

public int minimumTotal(List<List<Integer>> triangle) {
        int num = triangle.size();
        int[] min = new int[triangle.get(num-1).size()];
        for(int i=0;i<min.length;i++){
            min[i]=triangle.get(num-1).get(i);
        }
        for(int i=num-2;i>-1;i--){
            for(int j=0;j<triangle.get(i).size();j++){
                min[j]=triangle.get(i).get(j)+Math.min(min[j],min[j+1]);
            }
            
        }
        return min[0];
    }

업데이트 2015/08/26: 위의 코드 사고방식은 정확하지만 너무 교조적이어서 실제적으로 새로운 그룹을 만들지 않고 원본의list기록을 사용하여 바꾸면 된다.

public class Solution {
    /**
     * @param triangle: a list of lists of integers.
     * @return: An integer, minimum path sum.
     */
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        // write your code here
        int num = triangle.size();
        if (num == 0)
            return 0;
        for (int i = num - 2; i >= 0; i--){
            ArrayList<Integer> current = triangle.get(i);
            ArrayList<Integer> next = triangle.get(i + 1);
            for (int j = 0; j < current.size(); j++){
                current.set(j, current.get(j) + 
                    Math.min(next.get(j), next.get(j + 1)));
            }
        }
        return triangle.get(0).get(0);
    }
}

2.unique paths I/II
첫 번째 문제는 몇 개의 유일한 경로가 있느냐는 것이다. 이것은 행렬과 같은 큰 그룹을 만들어 각 노드에 도착하는 경로수를 저장해야 한다. 두 번째 문제는 장애를 추가했다. 이것은 영향을 주지 않는다. 장애에 부딪혔을 때 이 점의 경로수를 0으로 정리하면 된다.

public int uniquePaths(int m, int n) {
        if(m==0||n==0)return 1;
        int[][] pa = new int[m][n];
        
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0&&j==0)pa[0][0]=1;
                else if(i==0) pa[i][j]=pa[i][j-1];
                else if(j==0) pa[i][j]=pa[i-1][j];
                else pa[i][j]=pa[i][j-1]+pa[i-1][j];
            }
        }
        return pa[m-1][n-1];
    }

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m=obstacleGrid.length;
        int n=obstacleGrid[0].length;
        if(m==0||n==0)return 1;
        int[][] pa = new int[m][n];
        
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0&&j==0)pa[0][0]=1;
                else if(i==0) pa[i][j]=pa[i][j-1];
                else if(j==0) pa[i][j]=pa[i-1][j];
                else pa[i][j]=pa[i][j-1]+pa[i-1][j];
                if(obstacleGrid[i][j]==1) pa[i][j]=0;
            }
        }
        return pa[m-1][n-1];
    }

업데이트 08/04/2015: 이 두 문제 더 좋은 방법은 1차원 그룹만 사용하면 돼요.
업데이트 08/26/2015: 또 이 문제를 봤는데 우선 I 중의res[0]=1은 삭제할 수 있어 의미가 없다.이 두 문제의 사고방식은 모두 1차원 그룹을 사용하는데 매번res[j]를 계산할 때 그 안에 기록된 것은 바로 위쪽의 값이다.

public class Solution {
    /**
     * @param n, m: positive integer (1 <= n ,m <= 100)
     * @return an integer
     */
    public int uniquePaths(int m, int n) {
        // write your code here 
        int[] res = new int[n];
        for (int i = 0; i < n; i++){
            res[i] = 1;
        }
        for (int i = 1; i < m; i++){
            res[0] = 1;
            for (int j = 1; j < n; j++){
                res[j] = res[j] + res[j-1];
            }
        }
        return res[n-1];
    }
}

public class Solution {
    /**
     * @param obstacleGrid: A list of lists of integers
     * @return: An integer
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // write your code here
        int[] res = new int[obstacleGrid[0].length];
        for (int i = 0; i < obstacleGrid[0].length; i++){
            if (obstacleGrid[0][i] != 1){
                res[i] = 1;
            }else{
                while (i < obstacleGrid[0].length){
                    res[i] = 0;
                    i++;
                }
                break;
            }
        }
        for (int i = 1; i < obstacleGrid.length; i++){
            if (obstacleGrid[i][0] != 1 && res[0] != 0){
                res[0] = 1;
            }else{
                res[0] = 0;
            }
            for (int j = 1; j < obstacleGrid[0].length; j++){
                if (obstacleGrid[i][j] != 1){
                    res[j] = res[j] + res[j-1];
                }else{
                    res[j] = 0;
                }
            }
        }
        return res[obstacleGrid[0].length-1];
    }
}

3.minimal path sum
이 문제는 위 두 문제의 집합이다

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

Update 2015/08/26: 다음은 1차원 그룹 버전 해법입니다.이런 격자문제에 대해 2차원수조의 사고방식은 [0][0] 및 제1행과 제1열에 대해 단독으로 처리하는 것이다. 1차원수조의 사고방식은 먼저 제1행을 통해 수조를 초기화한 다음에 계산한 다음에 매 줄을 계산하지만 매번 처리 줄을 처리할 때 첫 번째 요소의 값을 단독으로 계산해야 한다.

public class Solution {
    /**
     * @param grid: a list of lists of integers.
     * @return: An integer, minimizes the sum of all numbers along its path
     */
    public int minPathSum(int[][] grid) {
        // write your code here
        int[] res = new int[grid[0].length];
        res[0] = grid[0][0];
        for (int i = 1; i < res.length; i++){
            res[i] = res[i - 1] + grid[0][i];
        }
        for (int i = 1; i < grid.length; i++){
            res[0] = res[0] + grid[i][0];
            for (int j = 1; j < res.length; j++){
                res[j] = grid[i][j] + Math.min(res[j - 1], res[j]);
            }
        }
        return res[res.length - 1];
    }
}

4.climb stairs
계단을 오르는 문제는 매번 한 걸음 두 걸음 모두 몇 가지 걷는 방법이 있는지 구할 수 있다.

public int climbStairs(int n) {
        if(n<2)return 1;
        int[] bu = new int[n+1];
        bu[0]=1;
        bu[1]=1;
        for(int i=2;i<=n;i++){
            bu[i]=bu[i-1]+bu[i-2];
        }
        return bu[n];
    }

5.word break
하나의 유수조로 여기 있는 이전의 직렬이 분할 가능한 직렬인지 저장합니다. 현재 부분을 제거하면 이 노드에서 뒤에 있는 직렬이 일치하는지 판단할 수 있습니다. 만약에true로 설정합니다.

public boolean wordBreak(String s, Set<String> dict) {
        boolean[] sa = new boolean[s.length()+1];
        sa[0]=true;
        for(int i=0;i<s.length();i++){
            if(!sa[i])continue;
            for(String tmp:dict){
                int len = tmp.length();
                if(i+len>s.length()) continue;
                if(s.substring(i,i+len).equals(tmp)) sa[i+len]=true;
            }
        }
        return sa[s.length()];
        
    }

Update 2015/08/26: 위의 제목이 면접에서 만났는데 면접관이 Trie로 해달라고 했어요.
6.jump game
엄밀히 말하면 이 문제는 dp를 사용하는 것이 아니다. 비록 dp는 풀 수 있지만 효율이 너무 낮다.

public boolean canJump(int[] A) {
        int max=0;
        int tp;
        for(int i=0;i<A.length;i++){
            if(i>max) return false;
            tp=i+A[i];
            if(tp>max) max=tp;
        }
        return true;
    }