java--study||O.o--动态规划

动规没写出来，抄的大佬滴

参考代码:

import java.util.Scanner;

public class Main
{	public static void main(String[] args)
	{	Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int[][] map = new int[n + 1][n + 1];
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++)
				map[i][j] = scanner.nextInt();
		scanner.close();
		
		int[] dp = new int[n + 1];//dp[i]为i到终点的最短距离
		int[] index = new int[n + 1];
		dp[n] = 0;
		for(int i = n - 1; i > 0; i--)//因为需要记录路径，从终点逆推
		{	dp[i] = Integer.MAX_VALUE;
			for(int j = i + 1; j <= n; j++)//(j > i),因为dp[j](j<=i)此时推不出来
			{	if(map[i][j] > 0 && dp[j] + map[i][j] < dp[i])
				{	dp[i] = dp[j] + map[i][j];
					index[i] = j;//当状态更新时,更新索引
				}
			}
		}
		System.out.println("minlong=" + dp[1]);
		int k = 1; 
		while(k > 0)
		{	System.out.print(k + " ");
			k = index[k];
		}
	}
}