<dp>最小换钱币数&&纸牌博弈问题&&机器人走路到达指定位置问题

public static int coins(int[] arr,int aim){
    if (arr == null || arr.length < 1 || aim < 0) {
        return 0;
    }
    return coinsProcess(arr,0,aim);
}

public static int coinsProcess(int[]arr, int index,int aim) {
    int res = 0;
    if (index != arr.length){
        for (int zhang = 0 ; arr[index] * zhang <= aim; zhang++){
            res += coinsProcess(arr,index + 1,aim - arr[index] *zhang);
        }
    }else {
        res = aim == 0 ? 1 : 0;
    }
    return res;
}

public static int coinsByDp(int[] arr,int aim){
    if (arr == null || arr.length < 1 || aim < 0) {
        return 0;
    }
    int[][] dp = new int[arr.length+1][aim+1];
    for (int i = 0 ; i < arr.length + 1; i++ ){
        dp[i][0] = 1;
    }
    for (int i = arr.length-1; i >= 0; i--){
        for (int j = 1; j <= aim ; j ++){
            dp[i][j] = dp[i+1][j] ;
            dp[i][j] += j - arr[i] >= 0 ? dp[i][j - arr[i]] : 0;
        }
    }
    return dp[0][aim];
}

array = {2,3,5} , aim = 10
dp[][] = 
1 0 1 1 1 2 2 2 3 3 4 
1 0 0 1 0 1 1 0 1 1 1 
1 0 0 0 0 1 0 0 0 0 1 
1 0 0 0 0 0 0 0 0 0 0

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];
}

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));

}

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]);
}

// 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;
}

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];
}

  System.out.println(ways(6,2,5,5));
  System.out.println(ways1(6,2,5,5)); 
  dp[][] = 
0 0 0 0 0 1 0 
0 0 0 0 1 0 1 
0 0 0 1 0 2 0 
0 0 1 0 3 0 2 
0 1 0 4 0 5 0 
0 0 5 0 9 0 5

  5
  5