[LeetCode - 알고리즘] 64. 최소 경로 와 (자바 구현)
6576 단어 LeetCode
마이너스 정 수 를 포함 하지 않 는 m x n 격자 를 지정 합 니 다. 왼쪽 상단 에서 오른쪽 하단 까지 의 경 로 를 찾 아 경로 의 숫자 합 계 를 최소 화 하 십시오.
설명: 매번 아래로 또는 오른쪽으로 한 걸음 만 이동 할 수 있 습 니 다.
예시:
:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
: 7
: 1→3→1→1→1 。
생각:
：
。 ， （i, j）
： （i-1, j） （i, j-1）
。 dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]。
코드 구현:
public int minPathSum(int[][] grid) {
// methods one : dynamic process (or can create another array arr[][])
// int[][] arr = new int[grid.length][grid[0].length];
for (int i = 1; i < grid.length; i++){
grid[i][0] += grid[i - 1][0];
}
for (int j = 1; j < grid[0].length; j++){
grid[0][j] += grid[0][j - 1];
}
for (int i = 1; i < grid.length; i++) {
for (int j = 1; j < grid[i].length; j++) {
grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
}
}
return grid[grid.length - 1][grid[0].length - 1];
}
전재 에 오신 것 을 환영 합 니 다. 전재 출처 를 밝 혀 주세요 【https://blog.csdn.net/sinat_35050808/article/details/84024146】
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
