1、前言
动态规划和分治算法非常类似，都是通过组合子问题的解来求解原问题。分治算法将问题划分为互不相交的子问题，而动态适应于子问题重叠的情况
动态规划常用于求解“最优化问题”，这类问题有很多个解，我们希望寻找最优解（最大值或最小值）
通常按如下四个步骤来设计一个动态规划算法：
- 刻画一个最优解的结构特征
- 递归地定义最优解的值
- 计算最优解的值，通常采用自底向上方法
- 利用计算出的信息构造一个最优解
或者说，动态规划有3个关键要素。
- 1、最佳子问题（将复杂问题转化成简单问题）
- 2、边界条件（一般是当数据量极少情况下的结果，比如n==0或n==1时的情况）
- 3、状态转移方程（考虑 n-1 和 n这两种规模时，结果之间的推导）
2、钢条切割问题
给定一段长为n的钢条和一个价格表，求解收益最大的钢条切割方案
钢条价格如上，怎么切割才能有最大收益呢？通过钢条价格，我们能手动计算出钢条最佳切割方案。
定义长为n的钢条切割最大收益为Rn，假设在k位置将钢条切成两段能获得最大收益，那么这两段k和n-k肯定也是最大收益，如果我们遍历循环，可得到如下公式：
最大收益为，不切割以及从1到n-1位置切割的收益最大值。
换一个角度重新考虑，如果从1到n-1位置切割，但左边的钢条不再切割，右边的钢条使用最佳方案切割。这样得到的会不是也是最佳切割方案呢？
很明显，这种做法也是正常的，想象最终切割结果，肯定也是符合这种模式的。这样简单的递归更利于编码。
动态规划的精髓在于保存子问题的解，以提高效率。在编码中我们新定义Rn，保存n长度的最大收益，并采用自底向上方法，即先求R0，R1，再求其它，如果单纯使用暴力递归的话，效率非常低。
public static int[] steel(int[] p){
int[] s = new int[p.length];
s[0] = 0;
int max = 0;
//因为长度为0的钢条，切割最大收益为0，S[0]已知，所以i从1开始
for (int i = 1; i < p.length; i++) {
max = 0;
for (int j = 1; j <= i; j++) {
//j也必须从1开始，如果从0开始，i等于1时，s[i-j]就等于s[1]了，而s[1]还是未知值
if (max < (p[j] + s[i-j])) {
max = p[j] + s[i-j];
}
}
s[i] = max;
}
return s;
}
2、最大子数组和
给出一个数组，求最大子数组和。例如给出如下数组，最大子数组和为20
-2, 11, -4, 13, -5, -2
此问题解题思路和1不一样。
仔细考虑，如果设长度为n的最大子数组和为Sn，那么Sn和Sn-1有什么关系呢？动态规划最重要的思想就是将大问题分解为子问题，并由子问题求解。
直接考虑Sn和Sn-1，好像二者没有任何关系，如果我们换个角度考虑，长度为n的数组，且以n结尾的最大子数组和为Sn，这么定义的话，那么根据Sn的值，如果Sn大于0，那么Sn+1等于Sn加上a[n]，如果小于0，那么Sn+1等于a[n]。
公式为：
dp[i+1] = max(dp[i]+a[i+1] , a[i+1])
public static int getMaxSubArray(int[] array){
int[] b = new int[array.length];
int max = 0;
b[0] = array[0];
max = b[0];
for (int i = 1; i < array.length; i++) {
if (b[i-1] > 0) {
b[i] = b[i-1] + array[i];
}else {
b[i] = array[i];
}
if (max < b[i]) {
max = b[i];
}
}
return max;
}
3、结语
动态规划还有其它经典问题，比如矩阵最少相乘次数，最长公共子序列，最优二叉搜索树等等。本文只讲了两个简单例子，简述动态规划的原理，可以更深入思考，二维的动态规划问题解决，以加深理解。
以上代码均已上传至本人的github，欢迎访问
