최단 경로(2D 행렬)

제목은 매트릭스 m을 정하고 왼쪽 상단부터 매번 오른쪽이나 아래로 갈 수 있으며 마지막으로 오른쪽 하단의 위치에 도달한다. 경로에 있는 모든 숫자를 누적하면 경로와 모든 경로 중 가장 작은 경로와 되돌아간다.예: 주어진 m은 다음과 같다. 1 3 5 9 8 1 3 4 5 0 6 1 8 4 0 경로 1, 3, 1, 0, 6, 1, 0은 모든 경로 중 경로와 가장 작기 때문에 12로 돌아간다.
해법 1
아이디어:
동적 기획을 사용하여 dp[M][N], M, N은 각각 행렬의 줄과 열 수 dp[i][j]를 정의하고 왼쪽 상단에서 행렬(i, j)의 위치가 가장 짧은 경로와 위치를 나타낸다.(i, j)의 위치는 두 가지 상황이 있음을 알 수 있다. 1) (i-1, j)에서 아래로 가고, 2) (i, j-1)에서 오른쪽으로 가기 때문에 dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+m[i][j];dp[0][j]는 dp[0][j-1]에서만 오른쪽으로 갈 수 있고, dp[i][0]는 dp[i-1][0]에서만 아래로 갈 수 있다.그래서 dp[0][j]=dp[0][j-1]+m[0][j], dp[i][0]=dp[i-1][0]+m[i][0].
코드:

package com.ch.evaluation.TestJava;

/**
 * @Auther: 011336
 * @Date: 2019/4/10 14:24
 */
public class ShortestRoad {
    public static void main(String[] args) {
        int arr[][] = new int[][]{{1,3,5,9},{8,1,3,4},{5,0,6,1},{8,8,4,0}};
        int shortNum = getRoad(arr);
        System.out.println(shortNum);
    }
    public static int getRoad(int arr[][])
    {
        int dp[][]=new int [arr.length][arr[0].length];
        dp[0][0]=arr[0][0];
        for(int i=1;i)
        {
            dp[i][0]=dp[i-1][0]+arr[i][0];
            //         
        }
        for(int j=1;j)
        {
            dp[0][j]=dp[0][j-1]+arr[0][j];
            //         
        }
        for(int i=1;i) {
            for (int j = 1; j < arr[0].length; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + arr[i][j];
            }
        }

        return dp[arr.length-1][arr[0].length-1];
    }
}

해법 2(최적화 해법 1)
사고방식: 해법1에서 dp수조의 공간 크기는 M*N이다. 사실 dp수조의 공간을 N으로 압축하고 크기는 N의 dp수조로 정의할 수 있다. 첫 번째 줄에 대해 dp[i]=dp[i-1]+m[0][i], 두 번째 줄의 dp[i]를 구할 때 첫 번째 줄의 dp[i], 두 번째 줄의 dp[i]=Math를 덮어쓸 수 있다.min(dp[i],dp[i-1])+m[i][j].
코드

public static int shortestRoad1(int arr[][])
    {
        int dp[]=new int[arr[0].length];
        dp[0]=arr[0][0];
        for(int j=1;j)
        {
            dp[j]=dp[j-1]+arr[0][j];
            //      dp
        }
        for(int i=1;i)
        {
            dp[0]=arr[i][0]+dp[0];
            //dp[0]         dp，
            //    dp      dp
            for(int j=1;j)
            {
                dp[j]=Math.min(dp[j-1]+arr[i][j], dp[j]+arr[i][j]);
            }
        }               
        return dp[arr[0].length-1];
    }

 
전재 대상:https://www.cnblogs.com/UncleWang001/p/10824095.html