動态規劃入門
一、多段圖問題(多階段決策)

已知兩點之間的花費,求從 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]);
}
}
如有錯誤或不合理的地方,敬請指正~
加油!!