动态规划的核心是要找到“状态”和“状态转移方程”，“状态"用来描述该问题的子问题的解。
/* * 基础解法,按照递归方法求解,该算法的运算时间是指数级增长的 * 这种算法对于相似的子问题进行了重复的计算，因此不是一种高效的算法 */public class FibonacciRecursion {//———–计算Fibonacci数列值的递归函数————–public static int fib(int n){if(n==1||n==2){//序列中第1,2个数为1return 1;}return fib(n-1)+fib(n-2);}public static void main(String[] args) {int i=46;long begin=System.currentTimeMillis();System.out.println("fib("+i+"):"+fib(i));long cost=System.currentTimeMillis()-begin;System.out.println("耗时:"+cost+"ms");}}
当n=5时，fib(5)的计算过程如下:
由上面可以看出，这种算法对于相似的子问题进行了重复的计算，，因此不是一种高效的算法。
下面采用动态规划的思想来求解
/* * 可以通过保存已经算出的子问题的解来避免重复计算 * 即使用动态规划的技术 */public class FibonacciDP {// ———-使用动态规划(DP)求fibonacci数列的值————public static int fib(int n) {int[] array = new int[n];//用来保存动态规划过程中的状态array[0] = 1;array[1] = 1;for (int i = 2; i < n; i++)array[i] = array[i – 1] + array[i – 2];//动态规划的状态转移式return array[n-1];}public static void main(String[] args) {long begin=System.currentTimeMillis();System.out.println("fib(46):"+fib(46));long cost=System.currentTimeMillis()-begin;System.out.println("耗时:"+cost+"ms");}}/* * 采用动态规划求解最长非降子序列的长度 */public class Lis {public static void main(String[] args) {int[] src = { 1, 2, 5, 3, 4, 9, 10, 6, 7, 8 };System.out.println("本例的最长非降子序列:1 2 3 4 6 7 8");System.out.println("<span style="line-height: 22.3999996185303px; font-family: sans-serif;">最长非降子序列长度</span>:" + lis(src));}public static int lis(int[] src) {int n = src.length;int[] dis = new int[n];// 保存"状态"的数组int len = 1;// 返回最大非降子序列的长度for (int i = 0; i < n; i++) {dis[i] = 1;for (int j = 0; j < i; j++) {if (src[j] < src[i] && dis[j] + 1 > dis[i])dis[i] = dis[j] + 1;}if (dis[i] > len) {len = dis[i];}}return len;}}参考文献(关于动态规划)
三人一条心，黄土变成金。
