算法之动态规划初步（Java版） 概述： 动规的使用场景： 示例例举及过程说明： 完整源代码下载：
算法的重要性是不言而喻的。
可能是你会不屑于听这样的话，是因为在我们的实际开发中，用到算法的地方真是太少了。对于这一点我并不否认，因为对于一个初级的开发者而言，算法显得太过高深了。如果我们想去实现一个功能，通常的做法就是百度或是Google。这就是为什么会有那么一句调侃之辞：我们不生产代码，我们只是代码的搬运工。
当我们已经完成了初级开发者的这一过程时，我们应该想着怎么去优化自己的代码，从而让自己的代码更加优美，也更显B格。
动规的使用场景：
动态规划是对回溯算法的一种改进。
我们知道回溯的一个致命缺点是它的重复计算，在后面的例子中我也会通过实例来说明这一点，而动规则规避了这个问题。动规的核心是状态和状态转移方程。
示例例举及过程说明：
1.数字三角形
问题描述：
有一个由非负整数组成的三角形，第一行只有一个数，除了最后一行之外每个数的左下方和右下方各有一个数。
从第一行的数开始，每次可以往下或右下走一格，直到走到最后一行，把沿涂经过的数全部加起来。如何走才能使得这个数尽可能的大？
思路梳理：
对于这样一个问题，可能大家想到的第一个解法就是递归。对于递归，我们不用想太多。因为当我们想要知道第(i, j)处的最大值时，是要依赖第(i + 1， j)和第(i + 1, j + 1)个节点的最大值。以此类推，如是我们就可以使用递归和递推来实现。
递归求解（关键代码）
/**
* 通过回溯法获得第(i, j)处的最大值
* @author Aaron
* 2015年8月2日
*/
private static int getNodeMaxByRecall(int[][] m, int i, int j) {
int max = Integer.MIN_VALUE;
System.out.println("m[" + i + "][" + j + "]");
max = m[i][j] + (i == m.length - 1 ? 0 : Math.max(getNodeMaxByRecall(m, i + 1, j), getNodeMaxByRecall(m, i + 1, j + 1)));
return max;
}
/**
* 回溯法求解
* @author Aaron
* 2015年8月1日
*/
public static void calculateByRecall(int[] a) {
int[][] m = getMatrix(a);
int max = getNodeMaxByRecall(m, 0, 0);
System.out.println("max[0][0] = " + max);
}
可以看到，递归求解时是一种自顶向下的求解方式。它是在按需去计算。
在递归中，比如说我们的意图是去求解max(i, j)，当我们知道需要求解max(i, j)，就必须知道max(i + 1, j)和max(i + 1, j + 1)时，我们才去求解max(i + 1, j)和max(i + 1, j + 1).
可是，这种按需求解的过程，无法让我们知道，再要计算的点是否已经计算过了。下面是这个程序在递归的过程中计算过的节点过程：
可以看到，这里有一些节点是被重复计算的。
递推法求解（关键代码）：
/**
* 通过递推法获得第(i, j)处的最大值
* @author Aaron
* 2015年8月2日
*/
private static int getNodeMaxByRecursion(int[][] m, int i, int j) {
int max = Integer.MIN_VALUE;
System.out.println("m[" + i + "][" + j + "]");
max = m[i][j] + (i == m.length - 1 ? 0 : Math.max(m[i + 1][j], m[i + 1][j + 1]));
return max;
}
/**
* 递推法求解
* @author Aaron
* 2015年8月2日
*/
private static void calculateByRecursion(int[] a) {
int[][] m = getMatrix(a);
for (int i = m.length - 1; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
m[i][j] = getNodeMaxByRecursion(m, i, j);
}
}
int max = m[0][0];
System.out.println("max[0][0] = " + max);
}
可以看到，递推求解时是一种自底向上的求解方式。它是在预先计算。
在递推中，比如说我们的意图是去求解max(i, j)，当我们知道需要求解max(i, j)，就必须知道max(i + 1, j)和max(i + 1, j + 1)时，不过这个时候，我们的max(i + 1, j)和max(i + 1, j + 1)已经计算出来了，这个时候我们就不用再去计算了.
在递推的计算过程中，因为我们是自底向上的求解，所以我们并不知道这个节点是否会被使用到，而如果这个节点需要被使用，我们也不会重复计算这个值，因为已经计算过，并已经保存下来了。不过，这个过程中，每个节点都会被计算一次，不管会不会被使用（虽然这个程序中是都被使用了）。
记忆化求解（关键代码）：
/**
* 通过记忆化搜索获得第(i, j)处的最大值
* @author Aaron
* 2015年8月2日
*/
private static int getNodeMaxByMemory(int[][] m, int[][] d, int i, int j) {
if (d[i][j] >= 0) {
return d[i][j];
}
System.out.println("m[" + i + "][" + j + "]");
d[i][j] = m[i][j] + (i == m.length - 1 ? 0 : Math.max(getNodeMaxByMemory(m, d, i + 1, j), getNodeMaxByMemory(m, d, i + 1, j + 1)));
return d[i][j];
}
/**
* 记忆化搜索
* @author Aaron
* 2015年8月2日
*/
private static void calculateByMemory(int[] a) {
int[][] m = getMatrix2(a);
int[][] d = initMatrix(m.length);
int max = getNodeMaxByMemory(m, d, 0, 0);
System.out.println("max[0][0] = " + max);
}
记忆化搜索是基于递归来进行的。因为我们想做一件事，来避免之前在递归中的重复计算。在学习算法的复杂度的时候，我们知道复杂度分为两种，一种是时间复杂度，一种是空间复杂度。这两种复杂度是有一个平衡的。也就是说我们想要在时间上优化，那么空间上就得做出牺牲。这里也正是使用了牺牲空间来换取时间的优先。
下面是各个节点被计算的过程：
这里可以看到，我们的每个节点也是只被计算了一次。节省了时间。
2.钢条切割
问题描述：
给定一段长度为n英寸的钢条和一个价格表p(i)，求切割钢条的方案，使得销售收益r(n)最大。注意，如果长度为n英寸的钢条的价格为p(n)足够大，最优解可能不是完全不需要切割。
价格表：
看到这一个问题，不知道大家是不是也跟我一样，第一感觉是可以使用贪心试一下。可是细想之后又发现行不通，因为这里面如果按不同的方式切割钢条，那么切割成的两份都是可变的量，不好控制。
按照上面的思路，我们可以使用两种方法来试着解决这一问题：
递归（关键代码）：
/**
* 计算长度为n的钢条的最佳切割方案(递归)
* @author Aaron
* 2015年8月3日
*/
private static int getMax(int[] p, int n) {
System.out.println(n);
if (n <= 0) {
return 0;
}
int max = Integer.MIN_VALUE;
for (int i = 1; i <= n; i++) {
max = Math.max(max, p[i - 1] + getMax(p, n - i));
}
return max;
}
/**
* 通过递归计算钢条的切割算法
* @author Aaron
* 2015年8月3日
*/
private static void calculateMaxByRecursive(int n) {
initPriceList();
int[] p = {1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
int max = getMax(p, n);
System.out.println("max = " + max);
}
记忆化搜索（关键代码）：
private static int[] getRecordArray(int n) {
if (n <= 0) {
return null;
}
int[] r = new int[n];
for (int i = 0; i < n; i++) {
r[i] = Integer.MIN_VALUE;
}
return r;
}
/**
* 计算长度为n的钢条的最佳切割方案(记忆化搜索)
* @author Aaron
* 2015年8月3日
*/
private static int getMaxByMemory(int[] p, int n, int[] r) {
if (n <= 0) {
return 0;
}
if (r[n] >= 0) {
return r[n];
}
System.out.println(n);
int max = Integer.MIN_VALUE;
for (int i = 1; i <= n; i++) {
max = Math.max(max, p[i - 1] + getMaxByMemory(p, n - i, r));
}
r[n] = max;
return max;
}
/**
* 通过记忆化搜索计算钢条的切割算法
* @author Aaron
* 2015年8月3日
*/
private static void calculateMaxByMemory(int n) {
initPriceList();
int[] p = {1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
int[] r = getRecordArray(n + 1);
int max = getMaxByMemory(p, n, r);
System.out.println("max = " + max);
}
完整源代码下载：
http://download.csdn.net/detail/u013761665/8957807