动态规划求二维网格中从左上角到右下角的最短路径( 每次只能向下、向右、向右下走 ) java 实现

dp[i][j] 表示在以点(0,0)作为左上角，点(i,i) 作为右下角的二维网格中 左上角到右下角的最短路径，
动态转移方程为：dp[i][j] = min{ dp[i][j-1],dp[i-1][j],dp[i-1][j-1] }.distance + weight[i][j]

ImageUtils.java：



import java.awt.*;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;
import javax.imageio.ImageIO;

public class ImageUtils {

    /**
     *
     * @param mat
     * @param outputPath
     * @param cellSize 格子的边长
     */
    public static void printMat2Image(int[][] mat, String outputPath,int cellSize,PathVO path) {
        // 总行数
        int rowCount = mat.length;

        // 总列数
        int colCount = mat[0].length;

        int fontSize = cellSize / 2;
        BufferedImage image = new BufferedImage(colCount * cellSize, rowCount * cellSize, BufferedImage.TYPE_INT_RGB);
        Graphics g = image.getGraphics();
        Random random = new Random();

        // 设置背景色为白色
        g.setColor(Color.WHITE);
        g.fillRect(0, 0, colCount * cellSize, rowCount * cellSize);

        // 画网格
        g.setColor(Color.BLACK);
        for (int i = 0; i <= rowCount; i++) {
            g.drawLine(0, i * cellSize, colCount * cellSize, i * cellSize);
        }
        for (int i = 0; i <= colCount; i++) {
            g.drawLine(i * cellSize, 0, i * cellSize, rowCount * cellSize);
        }

        Set<String> codes = new HashSet<>();
        List<PointVO> points = path.getPoints();
        for( PointVO point:points ){
            codes.add( point.getRowNum() + "_" + point.getColNum() );
        }

     /*   Color color = g.getColor();
        // 画路径
        List<PointVO> points = path.getPoints();
        g.setColor( Color.GREEN );
        for( PointVO point:points ){
            int x = point.getRowNum() * cellSize;
            int y = point.getColNum() * cellSize;
            g.fillRect(x, y, cellSize, cellSize); // 填充矩形
        }
        g.setColor( color );*/

        // 写入文本
        g.setFont(new Font("Arial", Font.BOLD, fontSize));
        Color color_old = g.getColor();
        Color color_green = Color.GREEN;
        FontMetrics fontMetrics = g.getFontMetrics();
        for (int rowNum = 0; rowNum < rowCount; rowNum++) {
            int[] row = mat[rowNum];
            for (int colNum = 0; colNum < colCount; colNum++) {
                int num = row[colNum];
                String code = rowNum + "_" + colNum;
                if( codes.contains( code ) ){
                    g.setColor( color_green );
                }else {
                    g.setColor( color_old );
                }
                String text = String.valueOf( num );
                int x = colNum * cellSize + (cellSize - fontMetrics.stringWidth(text) ) / 2;
                int y = rowNum * cellSize + (cellSize - fontMetrics.getHeight()) / 2 + fontMetrics.getAscent();
                g.drawString(text, x, y);
            }
        }

        // 输出图片
        try {
            ImageIO.write(image, "png", new File(outputPath));
            System.out.println("图片已生成：" + outputPath);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

PathVO.java：



import lombok.Getter;
import lombok.Setter;

import java.io.Serializable;
import java.util.List;


@Getter
@Setter
public class PathVO implements Serializable {

    private List<PointVO> points;
    private Integer distance;

}

PointVO.java：



import lombok.Getter;
import lombok.Setter;

import java.io.Serializable;


@Getter
@Setter
public class PointVO implements Serializable {
    private Integer rowNum;
    private Integer colNum;

    public PointVO(Integer rowNum, Integer colNum) {
        this.rowNum = rowNum;
        this.colNum = colNum;
    }
}

Test.java：



import lombok.Getter;
import lombok.Setter;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;



@Getter
@Setter
public class Test   {

    public static void main(String[] args) {
        test();
    }

    private static void test(){
     /*   int rowCount = 10;
        int colCount = 10;*/
        // int[][] mat = initRandomWeightMat( rowCount,colCount );
        int[][] mat = new int[][]{
                                    { 9, 9, 9, 9, 9, 9 },
                                    { 9, 1, 9, 9, 9, 9 },
                                    { 9, 1, 1, 9, 9, 9 },
                                    { 9, 1, 9, 1, 9, 9 },
                                    { 9, 1, 1, 1, 9, 1 },
                                    { 9, 9, 9, 9, 1, 9 }
                                };

        // dp[i][j] 表示在以点(0,0)作为左上角，点(i,i) 作为右下角的二维网格中 左上角到右下角的最短路径，
        // 动态转移方程为：dp[i][j] = min{ dp[i][j-1],dp[i-1][j] }.distance + weight[i][j]
        int rowCount = mat.length;
        int colCount = mat[0].length;

        PathVO[][] dp = new PathVO[rowCount][colCount];
        PathVO path = new PathVO();
        List<PointVO> points = new ArrayList<>();
        points.add( new PointVO( 0,0 ) );
        path.setPoints( points );
        path.setDistance( mat[0][0] );
        dp[0][0] = path;
        for (int colNum = 1; colNum < colCount; colNum++) {
            int rowNum = 0;
            int weight = mat[rowNum][colNum];
            PathVO path_prev = dp[rowNum][colNum - 1];
            path = new PathVO();
            points = new ArrayList<>();
            points.addAll( path_prev.getPoints() );
            points.add( new PointVO( rowNum,colNum ) );
            path.setPoints( points );
            path.setDistance( path_prev.getDistance() + weight );
            dp[rowNum][colNum] = path;
        }
        for (int rowNum = 1; rowNum < rowCount; rowNum++) {
            int colNum = 0;
            int weight = mat[rowNum][colNum];
            PathVO path_prev = dp[rowNum-1][colNum];
            path = new PathVO();
            points = new ArrayList<>();
            points.addAll( path_prev.getPoints() );
            points.add( new PointVO( rowNum,colNum ) );
            path.setPoints( points );
            path.setDistance( path_prev.getDistance() + weight );
            dp[rowNum][colNum] = path;
        }

        for (int rowNum = 1; rowNum < rowCount; rowNum++) {
            for (int colNum = 1; colNum < colCount; colNum++) {
                Integer weight = mat[ rowNum ][colNum];
                path = new PathVO();
                points = new ArrayList<>();

                // 当前点要么从上面的点到达，要么从 左边的点到达
                PathVO path_prev_up = dp[ rowNum -1 ][colNum];
                PathVO path_prev_left = dp[ rowNum ][colNum-1];
                PathVO path_prev_left_up = dp[ rowNum-1 ][colNum-1];
                PathVO path_prev_min = path_prev_up;
                if( path_prev_left.getDistance() < path_prev_min.getDistance() ){
                    path_prev_min = path_prev_left;
                }
                if( path_prev_left_up.getDistance() < path_prev_min.getDistance() ){
                    path_prev_min = path_prev_left_up;
                }
                points.addAll( path_prev_min.getPoints() );
                points.add( new PointVO( rowNum,colNum ) );
                path.setDistance( path_prev_min.getDistance() +  weight );
                path.setPoints( points );
                dp[ rowNum ][colNum] = path;
            }
        }
        path = dp[ rowCount -1 ][colCount -1];
        String outputPath = "C:\\E\\xxx.png";
        ImageUtils.printMat2Image( mat,outputPath,40,path );
    }

    private static int[][] initRandomWeightMat(int rowCount, int colCount) {
        Random random = new Random();
        // 初始化 二维网格矩阵
        int[][] mat = new int[rowCount][colCount];
        for (int rowNum = 0; rowNum < rowCount; rowNum++) {
            for (int colNum = 0; colNum < colCount; colNum++) {
                mat[ rowNum ][colNum] = random.nextInt( 2 ) + 1;
            }
        }
        return mat;
    }
}

测试输出：