动态规划算法和分治法的思想是类似的，将待求解问题分解成若干个子问题。但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。
动态规划基本步骤:
(1)找出最优解的性质，并刻划其结构特征。
(2)递归地定义最优值。
(3)以自底向上的方式计算出最优值。
(4)根据计算最优值时得到的信息，构造最优解。
2、编程题的递归方程分析
设计一个O(n2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。
输入有两行： 第一行：n，代表要输入的数列的个数 第二行：n个数，数字之间用空格格开
最长单调递增子序列的长度
在这里给出一组输入。例如：
5
1 3 5 2 9
在这里给出相应的输出。例如：
4import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner in = new Scanner(System.in); int n=in.nextInt(); int[] oldArray=new int[n]; for (int i = 0; i < oldArray.length; i++) { oldArray[i]=in.nextInt(); } lisGet(oldArray); } public static void lisGet(int[] arrayL ){ int[] lisLength=new int[arrayL.length]; for (int i = 0; i < arrayL.length; i++) { lisLength[i]=1; } int max=1; for (int i=1; i <arrayL.length;i++) { for (int j = 0; j <i; j++) { if (arrayL[j]<arrayL[i]&&(lisLength[j]+1)>lisLength[i]) { lisLength[i]=lisLength[j]+1; } if (max<lisLength[i]) { max=lisLength[i]; } } } System.out.println(max); } }
}
分析：本题我借用一个数组lisLength，以其下标i来辅助记录原数组第i到末尾的递增序列的元素个数，然后与max比较，得到最大的max
题目来源：王晓东，《算法设计与分析》
长江游艇俱乐部在长江上设置了n个游艇出租站1，2，…，n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j),1<=i<j<=n。试设计一个算法，计算出从游艇出租站1 到游艇出租站n所需的最少租金。
第1 行中有1 个正整数n（n<=200），表示有n个游艇出租站。接下来的第1到第n-1 行，第i行表示第i站到第i+1站,第i+2站, ... , 第n站的租金。
输出从游艇出租站1 到游艇出租站n所需的最少租金。
在这里给出一组输入。例如：
3
5 15
7
在这里给出相应的输出。例如：
12
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int[][]a = new int[105][105]; int []dp = new int[105]; int n =in.nextInt(); for(int i=1;i<n;i++){ for(int j=i+1;j<=n;j++){ a[i][j] = in.nextInt(); } } for(int i=0;i<105;i++){ dp[i]=99999; } dp[1]=0; for(int i=2;i<=n;i++) { for(int j=1;j<i;j++) { dp[i]=Math.min(dp[i],dp[j]+a[j][i]); } } System.out.println(dp[n]); } }
分析：借用数组dp来存放最小的费用，从最底层开始，逐层向上计算每两个站之间的最小花费，并记录在数组中，有记录的就不必再算了。
3、结对编程概况
我和我的同伴考虑过运用递归的算法，可在第一题得到的结果是部分正确，就换成其他的方式。对于这两道动态规划，我们都考虑到了数据运算过程可能会重复的现象，运用了数组对数据进行存放，避免重复计算。
原文：https://www.cnblogs.com/chenyuan404/p/9865135.html