1、斐波那契系類問題的遞歸和動態(tài)規(guī)劃
1.1 O(N)的解法
按照1驰后，1肆资，2，3灶芝，5.郑原。。的順序夜涕，依次求解即可犯犁。
package DynamicProgramming;
public class FibonacciSequenceV1 {
public static int getN(int n){
if(n<0)
return 0;
if(n==1 || n==2)
return 1;
int res = 1;
int pre = 1;
int temp = 0;
for(int i =3 ;i<=n;i++){
temp = res;
res = pre + res;
pre = temp;
}
return res;
}
public static void main(String[] args){
System.out.println(getN(10));
}
}
O(logN)的解法
主要用到了矩陣的思想，看下面的遞推公式：
package DynamicProgramming;
public class FibonacciSequenceV2 {
public static int[][] matrixPower(int[][] matrix,int p){
int[][] res = new int[matrix.length][matrix[0].length];
for(int i=0;i<matrix.length;i++){
res[i][i] = 1;
}
int[][] temp = matrix;
for(;p !=0; p >>= 1){
if((p & 1) == 1){
res = multiMatrix(res,temp);
}
temp = multiMatrix(temp,temp);
}
return res;
}
public static int[][] multiMatrix(int[][] m1,int[][] m2){
int[][] res = new int[m1.length][m1[0].length];
for(int i=0;i<m1[0].length;i++){
for(int j=0;j<m1.length;j++){
for(int k=0;k<m2.length;k++) {
res[i][j] += (m1[i][k] * m2[k][j]);
}
}
}
return res;
}
public static int getN(int n){
if(n<1)
return 0;
if(n==1 || n==2)
return 1;
int[][] matrix = {{1,1},{1,0}};
int[][] res = matrixPower(matrix,n-2);
return res[0][0] + res[1][0];
}
public static void main(String[] args){
System.out.println(getN(10));
}
}
2女器、矩陣的最短路徑和
使用動態(tài)規(guī)劃的方法酸役，建立dp數(shù)組，dp[i][j]代表從(0,0）位置到該處的最短路徑。當然涣澡，我們可以使用空間壓縮的方法贱呐，只用一維數(shù)組，保存每一行的結(jié)果入桂，這樣有效的降低的空間復(fù)雜度奄薇。
package DynamicProgramming;
public class minPathSum {
public static int getMinPath(int[][] distance){
int[] res = new int[distance[0].length];
for(int i=0;i<distance.length;i++){
for(int j=0;j<distance[0].length;j++){
if(i==0 && j==0)
res[j] = distance[0][0];
else if(i==0)
res[j] = distance[i][j] + res[j-1];
else if(j==0)
res[j] = distance[i][j] + res[j];
else
res[j] = Math.min(res[j],res[j-1]) + distance[i][j];
}
}
return res[distance[0].length-1];
}
public static void main(String[] args){
int[][] distance = {
{1,3,5,9},
{8,1,3,4},
{5,0,6,1},
{8,8,4,0}};
System.out.println(getMinPath(distance));
}
}
3、換錢最少的貨幣數(shù)
3.1 每種貨幣數(shù)量無限
在每種貨幣數(shù)量無限的情況下抗愁，使用動態(tài)規(guī)劃的方法馁蒂，從二維數(shù)組的角度出發(fā)，dp[i][j]代表使用arr[0,1..i]貨幣的情況下驹愚，組成j所需的最小張數(shù)远搪。后面使用空間壓縮的方法劣纲，可以將二維數(shù)組變?yōu)橐痪S數(shù)組逢捺。
值得注意的地方是，我們首先給一維數(shù)組全部賦值了max癞季，而不是使用默認值0劫瞳，max表示無法組成目標貨幣，0表示的是最少用0張就可以組成目標貨幣绷柒，這顯然是不合理的志于。
package DynamicProgramming;
public class minCoins {
public static int getMinCoins(int[] arr,int aim){
if(arr == null || arr.length == 0 || aim < 0)
return -1;
int[] res = new int[aim+1];
int max = Integer.MAX_VALUE;
for(int i=1;i<=aim;i++){
res[i] = max;
}
int leftup;
for(int i=0;i<arr.length;i++){
for(int j=0;j<=aim;j++){
if(i==0)
if(j>0 && j % arr[i] == 0)
res[j] = j / arr[i];
else{
leftup = max;
if(j >= arr[i] && res[j-arr[i]] != max)
leftup = res[j-arr[i]] + 1;
res[j] = Math.min(leftup,res[j]);
}
}
}
return res[aim] != max?res[aim]:-1;
}
public static void main(String[] args){
int[] arr = {5,2,3};
int aim = 20;
System.out.println(getMinCoins(arr,aim));
}
}
3.2 每種貨幣只能使用1張
思路跟上面的題目是一樣的，不過需要注意的一點是废睦，由于每張貨幣只能使用一次伺绽，因此我們在內(nèi)部遍歷每一行時，需要從后往前遍歷嗜湃。因為如果從前往后遍歷奈应，會出現(xiàn)硬幣被多次使用的情況。
package DynamicProgramming;
public class minCoinsV2 {
public static int getMinCoins(int[] arr,int aim){
if(arr == null || arr.length == 0 || aim < 0)
return -1;
int[] res = new int[aim+1];
int max = Integer.MAX_VALUE;
for(int i=1;i<=aim;i++){
res[i] = max;
}
if(arr[0] <= aim)
res[arr[0]] = 1;
int leftup;
for(int i=1;i<arr.length;i++){
for(int j=aim;j>0;j--){
leftup = max;
if(j >= arr[i] && res[j-arr[i]] != max)
leftup = res[j-arr[i]] + 1;
res[j] = Math.min(leftup,res[j]);
}
}
return res[aim] != max?res[aim]:-1;
}
public static void main(String[] args){
int[] arr = {5,2,3};
int aim = 20;
System.out.println(getMinCoins(arr,aim));
}
}
4购披、換錢的方法數(shù)
這里要注意的一點是杖挣，組成0元的方法是1種，而不是0種刚陡。
package DynamicProgramming;
public class MaxChangeCoinsMethod {
public static int getMaxCoinsMethod(int[] arr,int aim){
if(arr == null || arr.length == 0 || aim < 0)
return 0;
int[] res = new int[aim+1];
for(int j=0;j * arr[0] <= aim ;j++){
res[j * arr[0]] = 1;
}
for(int i=1;i<arr.length;i++){
for(int j=1;j<=aim;j++){
if(j >= arr[I])
res[j] += (res[j-arr[i]]);
}
}
return res[aim];
}
public static void main(String[] args){
int[] arr = {5,10,25,1};
int aim = 15;
System.out.println(getMaxCoinsMethod(arr,aim));
}
}
5惩妇、最長遞增子序列
package DynamicProgramming;
public class LongestIncreaseList {
public static int[] getLongestIncreaseList(int[] arr){
int[] ends = new int[arr.length];
ends[0] = arr[0];
int[] dp = new int[arr.length]; //以index對應(yīng)的數(shù)結(jié)尾的時候，最大遞增子序列的長度
int right = 0;
int l = 0;
int r = 0;
int m = 0;
for(int i=1;i<arr.length;i++){
l = 0;
r = right;
while(l<=r){
m = (r-l) / 2 + l;
if(ends[m]<=arr[I])
l = m + 1;
else
r = m - 1;
}
right = Math.max(l,right);
ends[l] = arr[I];
dp[i] = l + 1;
}
return dp;
}
public static int[] generateLIS(int[] arr,int[] dp){
int len = 0;
int index = 0;
for(int i=0;i<dp.length;i++){
if(dp[i] > len){
len = dp[i];
index = I;
}
}
int[] lis = new int[len];
lis[--len] = arr[index];
for(int i=index;i>=0;i--){
if(arr[i] < arr[index] && dp[i] == dp[index] - 1){
lis[--len] = arr[i];
index = I;
}
}
return lis;
}
public static void main(String[] args){
int[] arr = {2,1,5,3,6,4,8,9,7};
int[] dp = getLongestIncreaseList(arr);
int[] res = generateLIS(arr,dp);
for(int i=0;i<res.length;i++)
System.out.println(res[I]);
}
}
6筐乳、最長公共子序列問題
package DynamicProgramming;
public class LongestCommonSubStr {
public static int[][] findLongestSubStrDP(String str1,String str2){
char[] char1 = str1.toCharArray();
char[] char2 = str2.toCharArray();
int[][] dp = new int[char1.length][char2.length];
for(int i=0;i<char1.length;i++){
for(int j=0;j<char2.length;j++){
if(i==0){
dp[i][j] = (char2[j] == char1[i] ? 1:0);
}
else if(j==0){
dp[i][j] = (char2[j] == char1[i] ? 1:0);
}
else{
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
if(char1[i] == char2[j])
dp[i][j] = Math.max(dp[i][j],dp[i-1][j-1] + 1);
}
}
}
return dp;
}
public static String lcse(String str1,String str2,int[][] dp){
char[] char1 = str1.toCharArray();
char[] char2 = str2.toCharArray();
int m = char1.length-1;
int n = char2.length-1;
char[] res = new char[dp[m][n]];
int index = res.length-1;
while(index >= 0){
if(n>0 && dp[m][n] == dp[m][n-1])
n--;
else if(m>0 && dp[m-1][n] == dp[m][n])
m--;
else{
res[index--] = char1[m];
m--;
n--;
}
}
return String.valueOf(res);
}
public static void main(String[] args){
String str1 = "1A2C3D4B56";
String str2 = "B1D23CA45B6A";
int[][] dp = findLongestSubStrDP(str1,str2);
String res = lcse(str1,str2,dp);
System.out.println(res);
}
}
7歌殃、最長公共子串
子串和子序列是不一樣的趁怔， 子串必須是連續(xù)的庐舟，而子序列可以是不連續(xù)的。按照經(jīng)典的動態(tài)規(guī)劃方法欲间，我們得到如下思路：
但題目中要求的空間復(fù)雜度是O(1)贮懈，因此我們按照如下的思路匀泊，得到了正確的解決方法：
package DynamicProgramming;
public class LongestCommonSubString {
public static String getLongestCommonSubString(String str1,String str2){
if(str1==null || str2==null || str1.equals("") || str2.equals("")){
return "";
}
char[] char1 = str1.toCharArray();
char[] char2 = str2.toCharArray();
int row = 0;
int col = char2.length-1;
int max = 0;
int end = 0;
while(row < char1.length){
int i = row;
int j = col;
int len = 0;
while(i<char1.length && j<char2.length){
if(char1[i] == char2[j]){
len++;
}
else{
len = 0;
}
if(len > max){
max = len;
end = I;
}
I++;
j++;
}
if(col > 0){
col--;
}
else{
row++;
}
}
return str1.substring(end - max + 1,end + 1);
}
public static void main(String[] args){
String str1 = "1AB2345CD";
String str2 = "12345EF";
System.out.println(getLongestCommonSubString(str1,str2));
}
}
8优训、最小編輯代價
這里為什么會增加一列和一行，因為字符串是可以刪除為空串各聘，然后再通過插入操作來進行變換的揣非，如果沒有空串，會得到錯誤的答案躲因。
package DynamicProgramming;
public class MinEditCost {
public static int getMinEditCost(String str1,String str2,int ic,int dc,int rc){
if(str1==null || str2==null)
return 0;
char[] char1 = str1.toCharArray();
char[] char2 = str2.toCharArray();
int[] dp = new int[char2.length+1];
for(int j=0;j<char2.length+1;j++){
dp[j] = j * ic;
}
for(int i=1;i<char1.length+1;i++){
int pre = dp[0];
dp[0] = dc * I;
for(int j=1;j<char2.length+1;j++){
int tmp = dp[j];
if(char1[i-1] == char2[j-1]){
dp[j] = pre;
}
else{
dp[j] = pre + rc;
}
dp[j] = Math.min(dp[j],dp[j-1] + ic);
dp[j] = Math.min(dp[j],tmp + dc);
pre = tmp;
}
}
return dp[char2.length];
}
public static void main(String[] args){
String str1 = "abc";
String str2 = "adc";
int ic = 5;
int dc = 3;
int rc = 2;
if(str1.length() >= str2.length())
System.out.println(getMinEditCost(str1,str2,ic,dc,rc));
else
System.out.println(getMinEditCost(str2,str1,ic,dc,rc));
}
}
9早敬、龍與地下城游戲問題
與前面的題目不同的地方是，我們這里采用從右下角往左上角遍歷的順序大脉。但是動態(tài)規(guī)劃的思想都是一樣的搞监。
package DynamicProgramming;
public class MinHP {
public static int getMinHP(int[][] arr){
if(arr==null || arr.length==0 || arr[0].length==0)
return 0;
int[] dp = new int[arr[0].length];
for(int i=arr.length-1;i>=0;i--){
for(int j=arr[0].length-1;j>=0;j--){
if(i == arr.length-1 && j==arr[0].length-1)
dp[j] = arr[i][j] > 0 ? 1:1-arr[i][j];
else if(i==arr.length-1)
dp[j] = arr[i][j] > 0 ? dp[j+1]:dp[j+1] - arr[i][j];
else if(j==arr[0].length-1)
dp[j] = arr[i][j] > 0 ? dp[j]:dp[j] - arr[i][j];
else
dp[j] = arr[i][j] > 0 ? Math.min(dp[j],dp[j+1]) : Math.min(dp[j],dp[j+1]) - arr[i][j];
}
}
return dp[0];
}
public static void main(String[] args){
int[][] arr = {
{-2,-3,3},
{-5,-10,1},
{0,30,-5}};
System.out.println(getMinHP(arr));
}
}
10、表達式得到期望結(jié)果的組成種數(shù)
首先判斷express是否合理：
隨后使用動態(tài)規(guī)劃的方法：
package DynamicProgramming;
public class DesiredExpressionNum {
public static boolean isValid(char[] exp){
if((exp.length & 1) == 0)
return false;
for(int i=0;i<exp.length;i+=2){
if((exp[i] != '1') && (exp[i] != '0')){
return false;
}
}
for(int i=1;i<exp.length;i+=2){
if((exp[i] != '&') && (exp[i] != '|') && (exp[i]) != '^'){
return false;
}
}
return true;
}
public static int getDesiredExpressionNum(String express,boolean desired){
if(express == null || express.equals(""))
return 0;
char[] exp = express.toCharArray();
if(!isValid(exp))
return 0;
int[][] t = new int[exp.length][exp.length];//t[j][i] 表示express[j][i] 組成true的個數(shù)
int[][] f = new int[exp.length][exp.length];//f[j][i] 表示express[j][i] 組成false的個數(shù)
t[0][0] = exp[0] == '0' ? 0:1;
f[0][0] = exp[0] == '1' ? 0:1;
for(int i=2;i<exp.length;i+=2){
t[i][i] = exp[i] == '0'?0:1;
f[i][i] = exp[i] == '1'?0:1;
for(int j = i-2;j>=0;j-=2){
for(int k = j;k<i;k+=2){
if(exp[k+1] == '&'){
t[j][i] += t[j][k] * t[k+2][I];
f[j][i] += (f[j][k] + t[j][k]) * f[k+2][i] + f[j][k] * t[k+2][I];
}
else if(exp[k+1] == '|'){
t[j][i] += t[j][k] * f[k+2][i] + t[j][k] * t[k+2][i] + f[j][k] * t[k+2][I];
f[j][i] += f[j][k] * f[k+2][I];
}
else{
t[j][i] += f[j][k] * t[k+2][i] + t[j][k] * f[k+2][I];
f[j][i] += t[j][k] * t[k+2][i] + f[j][k] * f[k+2][I];
}
}
}
}
return desired?t[0][exp.length-1]:f[0][exp.length-1];
}
public static void main(String[] args){
String express = "1^0|0|1";
Boolean desired = false;
System.out.println(getDesiredExpressionNum(express,desired));
}
}
11镰矿、排成一條線的紙牌博弈游戲
package DynamicProgramming;
public class CardGameScore {
public static int getWinnerScore(int[] arr){
if(arr==null || arr.length==0)
return 0;
int[][] f = new int[arr.length][arr.length];
int[][] s = new int[arr.length][arr.length];
for(int j = 0;j<arr.length;j++){
f[j][j] = arr[j];
for(int i = j-1;i>=0;i--){
f[i][j] = Math.max(s[i+1][j] + arr[i],s[i][j-1] + arr[j]);
s[i][j] = Math.min(f[i+1][j],f[i][j-1]); //對手也是聰明決定的琐驴，我們能夠得到的是min的結(jié)果，取決于對方拿牌的情況秤标。
}
}
return Math.max(f[0][arr.length-1],s[0][arr.length-1]);
}
public static void main(String[] args){
int[] arr = {1,2,100,4};
System.out.println(getWinnerScore(arr));
}
}
12绝淡、跳躍問題
package DynamicProgramming;
public class JumpGame {
public static int getMinJumpTimes(int[] arr){
if(arr==null || arr.length==0)
return 0;
int times=0,cur=0,next=0;
for(int i=0;i<arr.length;i++){
if(cur < i){
times ++;
cur = next;
}
next = Math.max(next,i + arr[I]);
}
return times;
}
public static void main(String[] args){
int[] arr = {3,2,3,1,1,4};
System.out.println(getMinJumpTimes(arr));
}
}
13、N皇后問題
著名的N皇后問題苍姜，我們給出一種基于遞歸的方法牢酵。這里我們用了一個小trick，即用一個一維數(shù)組保存每一行皇后的問題衙猪，這樣馍乙，我們就可以只判斷列活著斜線上是否已經(jīng)放置了皇后即可。
package DynamicProgramming;
public class NQueenV1 {
public static boolean isValid(int row,int col,int[] record){
for(int i=0;i<row;i++){
if(record[i] == col || Math.abs(row-i) == Math.abs(record[i] - col))
return false;
}
return true;
}
public static int totalMethod(int index,int n,int[] record){
if(index == n){
return 1;
}
int res = 0;
for(int j =0;j<n;j++){
if(isValid(index,j,record)){
record[index] = j;
res += totalMethod(index + 1,n,record);
}
}
return res;
}
public static void main(String[] args){
int n = 8;
int[] record = new int[n];
System.out.println(totalMethod(0,n,record));
}
}
