专栏首页LeetCode<dp>最小换钱币数&&纸牌博弈问题&&机器人走路到达指定位置问题
原创

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

dp解法:

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

空间上优化的dp解法:

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

}

DP解法:

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

D解法:

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

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 2个线性表查找的优化

    实际上,如果待查的数据比较均匀,那么1/2是一个很好的选择,一旦待查数据中的数据是极度不均匀的,那么就需要考虑插值查找法。

    大学里的混子
  • LeetCode SingleNumber I,II,III

    Given a non-empty array of integers, every element appears twice except for one....

    大学里的混子
  • 数组问题

    输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字...

    大学里的混子
  • 运筹学教学|动态规划例题分析(一)

    作为运筹优化领域中一种极其重要的算法,动态规划可以说是非常skr好用了,那么为了方便大家的理解,这里给出几个了几个来源于《Operations Research...

    用户1621951
  • 运筹学教学 | 动态规划例题分析(一)

    作为运筹优化领域中一种极其重要的算法,动态规划可以说是非常skr好用了,那么为了方便大家的理解,这里给出几个了几个来源于《Operations Research...

    短短的路走走停停
  • HDUOJ----湫湫系列故事——减肥记I

    湫湫系列故事——减肥记I Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768...

    Gxjun
  • 组内刷题之LeetCode第188周赛解题思路

    题目:给你一个目标数组 target 和一个整数 n。每次迭代,需要从 list = {1,2,3..., n} 中依序读取一个数字。

    公众号guangcity
  • 网易笔试到底有多难,看看这篇就知道

    今天我要将的这道题是网易 8 月 3 号研发岗笔试的第一题,也是四道题中最简单的一道。这道题涉及到前缀和的应用,所以我想借这道题给大家讲一讲前缀和相关的一些知识...

    JAVA葵花宝典
  • InsetSort插入排序

    羊羽shine
  • 网易笔试到底有多难,看看这篇就知道

    今天我要将的这道题是网易 8 月 3 号研发岗笔试的第一题,也是四道题中最简单的一道。这道题涉及到前缀和的应用,所以我想借这道题给大家讲一讲前缀和相关的一些知识...

    乔戈里

扫码关注云+社区

领取腾讯云代金券