参考文章：http://www.360doc.com/content/13/0601/00/8076359_289597587.shtml
https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/
简介
动态规划简称DP，一般基于递归或一个或多个初始状态。当前问题可以由之前的已经解决的子问题推导得出。
入门
以硬币为例，假设有面值为V=（1,3,5）的硬币若干，给出一个值如11，求出最少可以使用这三种硬币凑足11，答案很简单为3。以下使用动态规划的思想求解：
设d[i]表示凑够i元至少需要d[i]个硬币，以下进行递推：
i=0：没有小于0的硬币，故d[0]=0
i=1：此时只有面值为1的硬币可用，故d[1]=1
i=2：此时依然只有面值为1的硬币可用，拿起面值为1的硬币，此时只要再凑足2-1的硬币即可，即d[1]的值，故d[2]=d[2-1]+1=2
i=3：此时可用的硬币为（1,3）
情况1：拿起面值为3的硬币，此时只要再凑足3-3的硬币即可，即d[0]的值，故d[3]=d[3-3]+1=1
情况2：拿起面值为1的硬币，此时只要再凑足3-1的硬币即可，即d[2]的值，故d[3]=d[3-1]+1=3
故d[3]=min{d[3-3]+1,d[3-1]+1}=2
i=4：此时可用的硬币为（1,3）
情况1：拿起面值为3的硬币，此时只要再凑足4-3的硬币即可，即d[1]的值，故d[3]=d[4-3]+1=2
情况2：拿起面值为1的硬币，此时只要再凑足4-1的硬币即可，即d[3]的值，故d[3]=d[4-1]+1=2
故d[4]=min{d[4-3]+1,d[4-1]+1}=2
总体思路为：当要求解d[i]时，先看V中可候选的元素[v1,v2,...,vi]，针对每一个选取的vi，都可以得到一个子问题d[i-vi],显然这个子问题已经求解过了，因此d[i]=min{d[i-vi]+1}。
（PS: d[i-vi]+1中的加1表示选取了一个vi，因此总数等于子问题的值加1）
代码如下：
package AlgorithmsBases;public class DynamicProgramming_01 { public static void main(String[] args) { // TODO Auto-generated method stub //有三种面值的硬币 int[] V = new int[] {1,3,5}; System.out.println("result:"+getBinNum(4,V)); } //value表示总值，V表示硬币面值，返回最少需要的硬币数目 public static int getBinNum(int value,int[] V){ int[] Min = new int[value+1]; Min[0]=0; //除了Min[0]以外，其余先设为最大值 for(int i=1;i 初级
接下来讨论一个经典问题：找出一个序列的最长非降子序列的长度（longest non-decreasing sequence）
比如V={5,3,4,8,6,7}的非降最长子序列为{3,4,6,7}，长度为4
设d[i]表示V中第i个元素对应的最长非降子序列的长度，求解思路如下：
i=1,V[i]=5：此时V[1]前面没有值，因此d[1]=1
i=2,V[i]=3：此时V[1:i-1]的元素中没有小于等于V[2]=3的值，因此d[2]=1
i=3,V[i]=4：此时V[1:i-1]的元素中小于等于V[3]的元素有{V[2]=3},因此d[3]=d[2]+1=2
i=4,V[i]=8：此时V[1:i-1]的元素中小于等于V[4]的元素有{V[2]=3，V[3]=4},因此d[4]=max{d[2]+1,d[3]+1}=mxa{2,3}=3
代码如下：
package AlgorithmsBases;public class DynamicProgramming_02 { public static void main(String[] args) { // int[] V = new int[] {5,3,4,8,6,7}; System.out.println("result:"+getLongestNonDecreasingSequence(V)); } //以下代码实现输入一个数组，输出最长非降子序列的长度 //比如{5,3,4,8,6,7}的非降最长子序列为{3,4,6,7}，长度为4 public static int getLongestNonDecreasingSequence(int[] V){ int[] MaxLen = new int[V.length]; //MaxLen最小值为1 for(int i=0;i =maxb) maxb=MaxLen[j]+1; } MaxLen[i]=maxb; } int max=0; for(int k=0;k
中级
有一个M*N的方格，每个格子都有一定数量的苹果，用V矩阵表示，从左上角出发，每次只能右移一步或下移一步，求解能获得的最大苹果数目。
这个问题属于二维动态规划，但思想与前面的问题类似。
设dp[i][j]表示我们走到第i行第j列的方格时能获得的最大苹果数目，则dp[i][j] = V[i][j] + max{dp[i-1][j],dp[i][j-1]}
代码如下：
package AlgorithmsBases;public class DynamicProgramming_03 { public static void main(String[] args) { // int[][] V = new int[][] { {1,2,1,1,2},{2,1,2,2,1},{1,1,2,2,1},{2,2,1,1,1},{1,1,2,1,2},{1,1,2,1,2}}; //printArray(V); System.out.println("result:"+getLongestNonDecreasingSequence(V)); } public static int getLongestNonDecreasingSequence(int[][] V){ int rows = V.length; int cols = V[0].length; int[][] dp = new int[rows][cols]; for(int i=0;i 0 && j>0){ dp[i][j]=V[i][j]+(dp[i-1][j]>dp[i][j-1]?dp[i-1][j]:dp[i][j-1]); } if(i>0&&j<=0){ dp[i][j]=V[i][j]+dp[i-1][j]; } if(i<=0&&j>0){ dp[i][j]=V[i][j]+dp[i][j-1]; } if(i<=0&&j<=0){ dp[i][j]=V[i][j]; } } } int max=0; for(int i=0;i