[하루하루 렛코드] #120.Triangle
하루에 한 번씩 Leet Code.
이 시리즈의 글은 이미 모두 제github에 업로드되었습니다, 주소: ZeeCoder's Github 저의 시나닷컴 웨이보에 관심을 가져 주십시오. 저의 시나닷컴 웨이보는 전재를 환영합니다. 전재는 출처를 밝혀 주십시오.
제목
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).
Note: Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
(2) 문제를 풀다
제목 대의: 삼각 행렬을 정하고 위에서 아래로 가는 경로와 가장 작은 경로를 구한다.매번 아래로 내려갈 때마다 인접한 수로만 갈 수 있다.
문제 풀이 사고방식: Note에서 언급한 공간 복잡도는 O[n]이고 n은 맨 아래 줄의 개수이다
이런 문제는 일반적으로 동적 계획을 생각하기 때문에 직접 이동 방정식으로 생각한다.dp[i][j]를 (i, j)점에서 최하단까지의 최소 경로로 기록합니다.n은 행렬의 깊이는 n-1행부터 dp[i][j]+=min(dp[i+1][j], dp[i+1][j+1])으로 계산하고 최종적으로 dp[0][0]가 구한 것이다.그래서 곧 코드를 썼습니다. 10msAC 버전입니다.
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
if(triangle.empty()) return 0;
vector<vector<int>> dp = triangle;
int n = dp.size();
if(n==1) return triangle[0][0];//
for(int i = n-2 ; i >=0 ; i--)
{
for(int j = 0 ; j < dp[i].size();j++)
{
dp[i][j] += min(dp[i+1][j],dp[i+1][j+1]);//
}
}
return dp[0][0];
}
};상기 코드를 최적화하여 공간의 복잡도를 낮추고 O(n)를 만족시키는 것을 고려하면 사실은 1차원 그룹만 사용하면 문제를 해결할 수 있다.다음 코드는 최적화된 버전, 8msAC입니다.
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
if(triangle.empty()) return 0;
int n = triangle.size();
vector<int> dp = triangle[n-1];//
for(int i = n-2 ; i >=0 ; i--)
{
for(int j = 0 ; j < triangle[i].size();j++)
{
dp[j] = triangle[i][j]+min(dp[j],dp[j+1]);
}
}
return dp[0];
}
};이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
