public static int coinsDp(int[] arr,int aim){
if (arr == null || arr.length < 1 || aim < 0) {
return 0;
}
int[] dp = new int[aim 1];
dp[0] = 1;
for (int i = arr.length-1; i >= 0; i--){
for (int j = 1; j <= aim ; j ){
dp[j] = j - arr[i] >= 0 ? dp[j-arr[i]]:0;
}
}
return dp[aim];
}
二、纸牌博弈问题
暴力解法：
代码语言：javascript复制
public static int win1(int []arr){
if (arr == null || arr.length < 1) return 0;
return Math.max(f(arr,0,arr.length-1),s(arr,0,arr.length-1));
}
public static int f(int[] arr, int i, int j){
if ( i == j)
return arr[i];
else return Math.max(arr[i] s(arr,i 1,j),arr[j] s(arr, i , j -1));
}
public static int s(int[] arr, int i, int j){
if ( i == j)
return 0;
else return Math.min(f(arr,i 1,j),f(arr, i , j -1));
}
DP解法：
代码语言：javascript复制
public static int win2(int []arr){
if (arr == null || arr.length < 1) return 0;
int[][] dpf = new int[arr.length][arr.length];
int[][] dps = new int[arr.length][arr.length];
for (int j = 0 ; j < arr.length;j ){
dpf[j][j] = arr[j];
}
for (int j = 0 ; j < arr.length;j ){
for (int i= j-1; i >= 0; i--){
dpf[i][j] = Math.max(arr[i] dps[i 1][j],arr[j] dps[i][j-1]);
dps[i][j] = Math.min(dpf[i 1][j],dpf[i][j-1]);
}
}
return Math.max(dpf[0][arr.length - 1],dps[0][arr.length -1]);
}
三、机器人走路到达指定位置问题
暴力解法：
代码语言：javascript复制
// 1 .. N 个位置
// M 来到的位置
// 剩余 P 步
// 最终要求落在K位置 10,5,20,2
public static int ways(int N, int M, int P, int K){
if (N < 2|| M < 1 || M > N || P < 0|| K < 1 || K > N) return 0;
// 固定参数是 N K 可变参数是 M P
if (P == 0 ){
return K == M ? 1 : 0;
}
int res;
if (M == 1) {
res = ways(N,M 1,P-1,K);
}else if (M == N) {
res = ways(N,M-1,P-1,K);
}else {
res = ways(N,M 1,P-1,K) ways(N,M-1,P-1,K);
}
return res;
}
D解法：
代码语言：javascript复制
public static int ways1(int N, int M, int P, int K){
if (N < 2|| M < 1 || M > N || P < 0|| K < 1 || K > N) return 0;
// 固定参数是 N K 可变参数是 M P
int[][] dp = new int[P 1][N 1];
dp[0][K] = 1;
for (int i = 1; i <= P;i ){
for (int j = 1; j <= N; j ){
dp[i][j] = (j 1 <= N ? dp[i-1][j 1]:0 ) (j-1 >= 1 ? dp[i-1][j-1] :0 ) ;
}
}
return dp[P][M];
}
