动态规划算法：
将待求解的问题分解为若干个子问题，按顺序求解子问题，前一子问题的解，为后一子问题的求解提供了有用的信息。
在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
为了节约重复求相同子问题的时间，引入一个数组，不管它们是否对最终解有用，把所有子问题的解存于该数组中，这就是动态规划法所采用的基本方法。
对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。
不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。
硬币找零：
public class Test{
public static void main(String[] args){
int[] arr = {10,15,5,2,1}; //随机生成不同面额的硬币，并存入数组中
int money = 63; // 生成需要找零的面额
int[] need = new int[money + 1]; //生成最小找零数的存储数组
zhaoling(arr,arr.length,money,need); //找零操作
}
public static void zhaoling(int[] arr, int n, int money, int[] need){
need[0] = 0; //定义 当需要找零0元时， 最小找零数为0
//从需要找一元硬币开始找零计算
for(int i=1;i<money;i++){
int minneed = i; // 定义默认最小找零数
//找零查找
for(int j=0;j<n;j++){
if(arr[j]<=i){
int count = need[i - arr[j]] + 1; //获得找零数
if(count < minneed){ //判断该找零数与默认找零数比较
minneed = count;
}
}
}
need[i] = minneed; //将需要找零i元时 所需要的找零数存入数组中
}
System.out.println("面值为"+(money)+"的最小找零硬币数为："+need[money]);
}
}
最长公共子序列：
public class Test{
public static void main(String[] args){
//输入两个字符串
String a = "abccbcd";
String b = "bcbdc";
//获得比较排序后的二维数组
int[][] arr = bestLong(a,b);
//输出最长公共子序列
System.out.print("最长公共子序列为：");
print(arr, a, b, a.length(), b.length());
}
public static int[][] bestLong(String a, String b){
//定义一个二维数组
int[][] max = new int[a.length()+1][b.length()+1];
for(int i=0;i<a.length();i++){
max[i][0] = 0;
}
for(int j=0;j<b.length();j++){
max[0][j] = 0;
}
for(int i=1;i<a.length();i++){
for(int j=1;j<b.length();j++){
if(a.charAt(i-1) == b.charAt(j-1)){
max[i][j] = max[i-1][j-1] + 1;
}else if(max[i-1][j] >= max[i][j-1]){
max[i][j] = max[i-1][j];
}else{
max[i][j] = max[i][j-1];
}
}
}
return max;
}
public static void print(int[][] arr, String a, String b, int i, int j){
if(i==0 || j==0){
return;
}
if(a.charAt(i - 1) == b.charAt(j - 1)) {
print(arr, a, b, i - 1, j - 1);
System.out.print(a.charAt(i - 1));
}else if (arr[i - 1][j] >= arr[i][j]) {
print(arr, a, b, i - 1, j);
}else {
print(arr, a, b, i, j - 1);
}
}
}