动态规划是最优化原理中的一种重要的方法。
动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费时间。
动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决。
总的来说，动态规划的优势在于：
问题描述:
动态规划举例
图10-3（a）示出了一个数字三角形，请编一个程序，
计算从顶至底的某处的一条路劲，
使该路劲所经过的数字的总和最大。
（1） 每一步可沿左斜线向下或右斜线向下；
（2） 1＜三角形行数≤100；
（3） 三角形中的数字为0，1，……99。
输入数据：
由INPUT.TXT文件中首先读到的是三角形的行数，
在例子中INPUT.TXT表示如图13-3（b）.
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
5 6 9 5 9 8
从别人blog里看到这个题目,手上痒痒,就写了一个.用的是逆向递推法从顶部往下.
分2个文件,一个主程序和一个用于读取文件的辅助类.
思路:
1.算出每个节点的规划值(也就是待比较的最大值),并记录搜索路径
2.取三角形底边所有规划值中的最大值
3.输出路径
主程序
package
test;
import
java.util.
*
;
/** */
/**
* 用动态规划法求出最优路径
*
@author
zqc
*
*/
public
class
DynamicSolveTrianglePath
{
private
String[][] str_triangle
=
null
;
private
Node[][] triangle_nodes
=
null
;
private
List nodes;
private
List paths;
//
节点
static
class
Node
{
private
int
value;
private
List path
=
new
Vector();
public
List getPath()
{
return
path;
}
public
void
setPath(List p)
{
path
=
p;
}
//
n=(0,0) or (0,1) or (2,2)
public
void
addPath(String n)
{
path.add(n);
}
public
void
addPath(List pa)
{
path.addAll(pa);
}
public
int
getValue()
{
return
value;
}
public
void
setValue(
int
value)
{
this
.value
=
value;
}
}
public
DynamicSolveTrianglePath()
{
initNodes();
findPath();
}
// 从根节点开始,逆向推解出到达所有节点的最佳路径
private void initNodes(){
this.str_triangle = ReadTriangle.getTriangle();
triangle_nodes = new Node[str_triangle.length][];
nodes = new Vector();
for(int i = 0 ; i < str_triangle.length; i++){
triangle_nodes[i] = new Node[str_triangle[i].length];
for(int j = 0 ; j<str_triangle[i].length;j++){
String currentPath = "("+i+","+j+")";
Node n = new Node();
if(i==0&&j==0){
n.setValue(
c(str_triangle[0][0])
);
n.addPath(currentPath);
triangle_nodes[i][j] = n;
continue;
}
//左右边界节点
if((j==0||j==str_triangle[i].length-1)){
if(i==1){//第2行的节点
int value = c(str_triangle[0][0])+c(str_triangle[i][j]);
List ph = triangle_nodes[0][0].getPath();
n.addPath(ph);
n.addPath(currentPath);
n.setValue(value);
ph = null;
}else{//0,1行以下的其他边界节点
int value = j==0?c(str_triangle[i][j])+triangle_nodes[i-1][j].getValue():
c(str_triangle[i][j])+triangle_nodes[i-1][j-1].getValue();
List ph = j==0?triangle_nodes[i-1][j].getPath():
triangle_nodes[i-1][j-1].getPath();
n.addPath(ph);
n.addPath(currentPath);
n.setValue(value);
}
}else{//除边界节点外其他节点
Node node1 = triangle_nodes[i-1][j-1];
Node node2 = triangle_nodes[i-1][j];
Node bigger = max(node1,node2);
List ph = bigger.getPath();
n.addPath(ph);
n.addPath(currentPath);
int val = bigger.getValue()+c(str_triangle[i][j]);
n.setValue(val);
}
triangle_nodes[i][j] = n;
n = null;
}//end of for j
}//end of for i
}
private Node max(Node node1,Node node2){
int i1 = node1.getValue();
int i2 = node2.getValue();
return i1>i2?node1:node2;
}
private int c(String s){
return Integer.parseInt(s);
}
//找出最佳路径
private void findPath(){
if(this.triangle_nodes==null)return;
int max = 0;
int mi = 0;
int mj = 0;
for(int i = 0 ; i < triangle_nodes.length; i++){
for(int j = 0 ; j<triangle_nodes[i].length;j++){
int t = triangle_nodes[i][j].getValue();
if(t>max){
max = t;
mi = i;
mj = j;
}
}
}
System.out.println("Max Path:"+triangle_nodes[mi][mj].getPath());
System.out.println("Max Value:"+max);
}
public static void main(String[] args)throws Exception{
DynamicSolveTrianglePath dsp = new
DynamicSolveTrianglePath();
}
}
用于读取文件的辅助类
package
test;
import
java.io.
*
;
import
java.util.
*
;
/** */
/**
* 输入文本格式为
* 类似这样一个数字三角形
*
* x
* x x
* x x x
* x x x x
* x x x x x
*
*
@author
zqc
*
*/
public
class
ReadTriangle
{
public
static
String TRIANGLE_FILE
=
"
d:/triangle.txt
"
;
public
static
String[][] getTriangle()
{
String[][] rtn;
try
{
File f
=
new
File(ReadTriangle.TRIANGLE_FILE);
BufferedReader br
=
new
BufferedReader(
new
FileReader(f)
);
List l
=
new
Vector();
String line
=
br.readLine();
while
(line
!=
null
)
{
l.add(line.trim());
line
=
br.readLine();
}
int
heigth
=
l.size();
rtn
=
new
String[heigth][];
for
(
int
i
=
0
; i
<
heigth ; i
++
)
{
String s
=
(String)l.get(i);
String[] tk
=
s.split(
"
"
);
int
tklen
=
tk.length;
rtn[i]
=
new
String[tklen];
for
(
int
k
=
0
; k
<
tklen ; k
++
)
{
rtn[i][k]
=
tk[k];
}
}
return
rtn;
}
catch
(FileNotFoundException e)
{
e.printStackTrace();
}
catch
(IOException e)
{
e.printStackTrace();
}
return
null
;
}
}
结果输出如下:
Max Path:[(0,0), (1,0), (2,0), (3,1), (4,1), (5,2)]
Max Value:39
同样的方法可以解决很多类似的问题,比如,游戏中的最短路径;最优化投资问题;背包问题等等.