[DP]120. Triangle

제목 링크: 120.Triangle – medium 문제 이해다음 단계는 이 노드의 왼쪽 결점 또는 오른쪽 결점이어야 합니다. 즉, 현재 열number는 i이고, 다음 단계는 i 또는 i+1입니다.
아이디어는 대신을 참고하여 매우 상세하다.https://kingsfish.github.io/2017/08/26/Leetcode-120-Triangle/이 문제의 관건은 아래에서 위로의DP를 사용하는 데 있다.
이 두 문제를 어떻게 해결할 것인가를 생각할 때 갑자기 2차원 DP 문제를 생각할 때 공간 최적화 방법이 생각났다. 2차원 DP 문제도 수치를 잃어버리는 문제가 있는데 이것은 역순으로 이 문제를 해결하는 것이다.
이 문제를 운용할 때 우리는 자정에서 아래로 자정으로 바꿀 수 있다. 매번 이 노드의 두 아이의 수치 크기를 비교할 때마다 작은 그 아이의 노드의 값에 자체 노드의 값을 더하면 이 노드 이하의 최소 경로와 이를 정점까지 유추할 수 있다.이 두 가지 방식은 결과의 정확성에 아무런 영향을 미치지 않는다. 그러면 첫 번째 수치 저장 문제를 해결할 수 있고 우리는 이렇게 하면 두 번째 문제를 해결할 수 있다는 것을 발견했다. 이 알고리즘에 따라 마지막 최소 경로와 틀림없이 dp(0)에 저장될 것이다. 그러면 마지막으로 dp에 대한 반복 시간을 절약할 수 있다.
이 알고리즘은 결과를 저장하기 위해 1차원 그룹을 사용했는데 공간 복잡도는 O(n)(n은 삼각형 층수)이다.동시에 이 알고리즘은 두 층의 순환이 있기 때문에 시간 복잡도는 O(n^2)이다.

class Solution {
    public int minimumTotal(List> triangle) {
        if(triangle == null || triangle.size()== 0)return 0;
        
        int[] dp = new int[triangle.size()+1];//         num，       size＝＝  ;         ，size＋1
        //    
        for(int i = triangle.size()-1; i>=0; i--){
            List sublist = new ArrayList(triangle.get(i));
            for(int j = 0; j< sublist.size(); j++){
                dp[j] = Math.min(dp[j], dp[j+1])+sublist.get(j);//start->    ，    ；   ->min(left_path,right_path)+self
            }
        }
        return dp[0];
        
    }
}