動态規劃入門

一、多段圖問題（多階段決策）

已知兩點之間的花費，求從 0 點到 9 點的最小花費路徑。

思路

對多段圖的邊(u, v)，用

表示邊上的權值，将從源點s到終點t的最短路徑記為d(s, t)

則從源點0到終點9的最短路徑d(0, 9)由下式确定：

而對于從1--9、2--9、3--9的最小花費，可由下式表示：

......

依次類推，最後遞推到7--9、8--9的最小花費，此條件是已知條件。這樣再回溯回來，便可以依次求得各個值，最終得到題意中要求的解，需要從底向上的求解。

該題特點：有向、可分段

import java.util.Scanner;
public class Main{
	static final int MAX = 1000000;
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		
		int[][] c = new int[15][255]; // i->j的權值（邊）
		int[] cost = new int[15]; //從0到i的最小花費
		int[] path = new int[15]; //記錄最優解
		int n = cin.nextInt(); //頂點數
		int m = cin.nextInt(); //邊數
		
		//初始化
		for(int i=0; i<n; i++) {
			for(int j=i+1; j<n; j++) {
				c[i][j] = MAX;
				c[j][i] = MAX;
			}
			cost[i] = MAX;
		}
		cost[0] = 0;
		path[0] = -1;
		
		//邊指派
		for(int i=0; i<m; i++) {
			int u = cin.nextInt();
			int v = cin.nextInt();
			int w = cin.nextInt();
			c[u][v] = w;
		}
		
		for(int i=1; i<n; i++) {
			for(int j=0; j<i; j++) {
				if(cost[i] > c[j][i] + cost[j]) {
					cost[i] = c[j][i] + cost[j];
					path[i] = j;
				}
			}
		}
		
		System.out.println("最小花費：" + cost[n-1]);
		
		System.out.print("最優解：9 " + path[n-1] + " ");
		int i = path[n-1];
		while(path[i] >= 0) {
			System.out.print(path[i] + " ");
			i = path[i];
		}
	}
}
/**

輸入樣例：
10 18
0 1 4
0 2 2
0 3 3
1 4 9
1 5 8
2 4 6
2 5 7
2 6 8
3 5 4
3 6 7
4 7 5
4 8 6
5 7 8
5 8 6
6 7 6
6 8 5
7 9 7
8 9 3

輸出樣例：
16
0 3 5 8 9

*/
           

運作結果：

二、聰明的KK

有一個N*M的矩形沙漠，一個小動物“KK”正從沙漠區域的左上角沿着向右或向下的方向往右下角跑去。KK太聰明了，它居然能在跑的過程中會選擇吃掉盡可能多的蟲子線路。

輸入樣例：

3 4

3 1 2 8

5 3 4 6

1 0 2 3

輸出樣例：

24

思路

找到相關的遞推方程（cost[i][j] 表示從開始到 i,j 點的最大花費）

cost[i][j] = cost[i][j] + max(cost[i-1][j], cost[i][j-1]);

import java.util.Scanner;
public class Main{
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		
		int n = cin.nextInt(); //行數
		int m = cin.nextInt(); //列數
		int[][] cost = new int[15][15];//從開始到i,j點的最大花費
		
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=m; j++) {
				cost[i][j] = cin.nextInt();
			}
		}

		for(int i=1; i<=n; i++) {
			for(int j=1; j<=m; j++) {
				int c = cost[i-1][j] > cost[i][j-1] ? cost[i-1][j] : cost[i][j-1];
				cost[i][j] += c;
			}
		}
		
		System.out.println(cost[n][m]);
	}
}
           

如有錯誤或不合理的地方，敬請指正~

加油！！