動態規劃算法：
將待求解的問題分解為若干個子問題，按順序求解子問題，前一子問題的解，為后一子問題的求解提供了有用的信息。
在求解任一子問題時，列出各種可能的局部解，通過決策保留那些有可能達到最優的局部解，丟棄其他局部解。依次解決各子問題，最后一個子問題就是初始問題的解。
為了節約重復求相同子問題的時間，引入一個數組，不管它們是否對最終解有用，把所有子問題的解存于該數組中，這就是動態規劃法所采用的基本方法。
對每一個子問題只解一次，將其不同階段的不同狀態保存在一個二維數組中。
不管該子問題以后是否被用到，只要它被計算過，就將其結果填入表中。這就是動態規劃法的基本思路。

硬幣找零：
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);
}

}

}