LeetCode120—Triangle

LeetCode120—Triangle
원제
https://leetcode.com/problems/triangle/
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle [ [2], [3,4], [6,5,7], [4,1,8,3] ] The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
분석 1
여기서 가장 간단한 사고방식은 2차원 동태 기획이다. 한 i행 j열의 요소에 대해 말하자면 이 요소의 가장 짧은 경로의 한 단계는 i-1행 j열의 요소일 수도 있고 i-1행 j+1열의 요소일 수도 있다(이곳에서 우리는 경계 조건을 고려해야 한다).만약 dp[i][j]가 i행 j열 요소의 가장 짧은 경로를 나타낸다.그러면 동귀방정식은 간단하게 이렇게 쓸 수 있다. dp[i][j]=min(dp[i-31][j], dp[i-31][j-31])+triangle[i][j](1)
코드 1
상술한 방정식에 근거하여 코드를 쓰지만 두 가지를 주의해야 한다.경계 조건 고려 2.마지막 줄을 한 번 순환해서 최소값을 얻습니다

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int len = triangle.size();
        vector<vector<int>>dp(len, vector<int>(len));
        if (0 == len)
            return 0;
        dp[0][0] = triangle[0][0];
        for (int i = 1; i < len; i++)
        {
            for (int j = 0; j < i + 1; j++)
            {
                if (j>0 && j != i)
                    dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j];
                else if (j == i)//   
                    dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
                else//   
                    dp[i][j] = dp[i - 1][j] + triangle[i][j];
            }
        }
        int minVal = dp[len - 1][0];//    
        for (int i = 1; i < len; i++)
        {
            if (dp[len - 1][i] < minVal)
                minVal = dp[len - 1][i];
        }
        return minVal;
    }
};

분석2
여전히 2차원 그룹의 동적 기획이지만 우리는 아래에서 위로 올라갈 수 있다. 그러면 i행 j열의 원소에 대해 이 원소의 가장 짧은 경로의 마지막 단계는 i+1행 j열 또는 i+1행 j+1열에서 나올 수 있다. 이런 상황은 경계 상황을 고려할 필요가 없다. 왜냐하면 i+1행은 항상 i행보다 한 원소가 많기 때문이다.
만약 dp[i][j]가 i행 j열 요소의 가장 짧은 경로를 나타낸다.그러면 동귀방정식은 간단하게 이렇게 쓸 수 있다. dp[i][j]=min(dp[i+1][j], dp[i+1][j+1])+triangle[i][j](2)
코드 2

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int len = triangle.size();
        vector<vector<int>>dp(len, vector<int>(len));
        if (0 == len)
            return 0;
        for (int i = 0; i < len; i++)
            dp[len - 1][i] = triangle[len - 1][i];
        for (int i = len - 2; i >= 0; i--)//    
        {
            for (int j = 0; j < i + 1; j++)
            {
                dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j];
            }
        }
        return dp[0][0];
    }
};

분석하다
이것이 바로 인터넷 대신의 사고방식을 참고한 것이다.http://blog.csdn.net/linhuanmars/article/details/23230657또한 위에서 아래로 내려가는 것과 아래에서 위로 올라가는 두 가지 상황으로 나뉘는데 같은 위에서 아래로 내려가는 것은 경계 조건을 고려해야 한다.이런 방법은 O(n)의 공간 복잡도만 사용한다.
코드 3

//    
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int len = triangle.size();
        if (0 == len)
            return 0;
        vector<int>dp(len);
        dp[0] = triangle[0][0];
        for (int i = 1; i < len; i++)
        {
            //dp[i] = dp[i - 1] + triangle[i][i];
            for (int j = i; j >= 0; j--)//        
            {
                if (0 == j)
                    dp[j] = dp[j] + triangle[i][j];
                else  if (i == j)
                    dp[j] = dp[j - 1] + triangle[i][j];
                else
                    dp[j] = min(dp[j], dp[j - 1]) + triangle[i][j];//dp[j]->     ,dp[j-1]     
            }
        }
        int minVal = dp[0];
        for (int i = 0; i < dp.size(); i++)
        {
            if (dp[i] < minVal)
                minVal = dp[i];
        }
        return minVal;
    }
};

코드 4

//    
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int len = triangle.size();
        vector<vector<int>>dp(len, vector<int>(len));
        if (0 == len)
            return 0;
        for (int i = 0; i < len; i++)
            dp[len - 1][i] = triangle[len - 1][i];
        for (int i = len - 2; i >= 0; i--)
        {
            for (int j = 0; j < i + 1; j++)
            {
                dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j];
            }
        }
        return dp[0][0];
    }
};