纸牌博弈问题--动态规划(java)

这篇具有很好参考价值的文章主要介绍了纸牌博弈问题--动态规划(java)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

纸牌博弈题目描述

给定一个整型数组arr,
代表数值不同的纸牌排成一条线
玩家A和玩家B依次拿走每张纸牌 规定玩家A先拿,
玩家B后拿
但是每个玩家每次只能拿走最左或最右的纸牌
玩家A和玩家B都绝顶聪明 (都在拿最优解)
请返回最后获胜者的分数

暴力递归

解题思路.
递归就是可虑所有可能性,然后比较出最值,
因此递归就是,不断比较我拿左边和拿右边时,哪个是最优解.
此时.难点在于,还有个后手拿牌的B.
他也是要拿当前的最优解,
这就形成了一个嵌套.
A 拿完一张后,他后面拿牌要在B 拿完后再拿,
两个嵌套的递归思路就形成了,

代码演示

  /**
     * 暴力递归求最值
     * @param arr
     * @return
     */
    public static int win(int[]arr){
        if (arr == null || arr.length == 0){
            return 0;
        }
        //先手
        int f = f(arr, 0, arr.length - 1);
        //后手
        int g = g(arr,0, arr.length - 1) ;
        return Math.max(f,g);
    }

    /**
     * 先手可以拿到的最大值
     * @param arr
     * @param L
     * @param R
     * @return
     */
    public static int f(int[]arr,int L,int R){
    //base case 剩一张 就归先手方
        if(L == R){
            return arr[L];
        }
        //选择一张牌后,剩下要在后手选择后的里继续做选择,
        //后手方也有两种选择情况,都列出来,
        int p1 = arr[L] + g(arr,L + 1,R);
        int p2 = arr[R] + g(arr,L,R - 1);
        //我们取最优解
        return Math.max(p1,p2);
    }

    /**
     * 后手可以拿到的最大值
     * @param arr
     * @param L
     * @param R
     * @return
     */
    public static int g(int[]arr,int L,int R){
    	//剩一张时,后手方啥都拿不到,因为先手会拿走.
        if (L == R){
            return 0;
        }
        //先手拿牌后,后手方只能在先手选择剩下的里去先择
        //因此把先手拿牌的两种情况都算出来
        int g1 = f(arr,L + 1,R);
        int g2 = f(arr,L,R - 1);
        //取最小值是因为,先手一定会把当前最优解拿走,
        //留给后手方一个差一点的值,所以取最小
        return Math.min(g1,g2);
    }

递归 + 缓存

找出暴力递归重复计算的地方,
放进缓存,
这里面重复计算的是什么呢.
就是L R 位置选择会有不断的重复.
用缓存做成记忆化搜索,

代码演示

   /**
     * 递归加缓存求最值
     * @param arr
     * @return
     */
    public static int maxCards(int[]arr){
        if (arr == null || arr.length == 0){
            return 0;
        }
        int N = arr.length;;
        //缓存先手拿牌的最值问题
        int[][]fs = new int[N][N];
        //缓存后手拿牌的最值问题
        int[][]gs = new int[N][N];
        for (int i  = 0;i < N ;i++){
            for (int j = 0; j < N;j++){
                fs[i][j] = -1;
                gs[i][j] = -1;
            }
        }
        int f1 = f1(arr, 0, N - 1, fs, gs);
        int g1 = g1(arr, 0, N - 1, fs, gs);
        return Math.max(f1,g1);
    }

    /**
     * 和递归是一样的,只是把结果放进缓存里.
     * @param arr
     * @param L
     * @param R
     * @param fs
     * @param gs
     * @return
     */
    public static int f1(int[]arr,int L,int R,int[][]fs,int[][]gs){
        if (fs[L][R] != -1){
            return fs[L][R];
        }
        int ans = 0;
        if(L == R){
            ans = arr[L];
        }else {
            int p1 = arr[L] + g1(arr,L + 1,R,fs,gs);
            int p2 = arr[R] + g1(arr,L ,R - 1,fs,gs);
            ans = Math.max(p1,p2);
        }
        fs[L][R] = ans;
        return ans;
    }

    /**
     *
     * @param arr
     * @param L
     * @param R
     * @param fs
     * @param gs
     * @return
     */
    public static int g1(int[]arr,int L,int R,int[][]fs,int[][]gs){
        if (gs[L][R] != -1){
            return gs[L][R];
        }
        int ans = 0;
        if (L != R){
            int p1 = f1(arr,L + 1,R,fs,gs);
            int p2 = f1(arr,L,R - 1,fs,gs);
            ans = Math.min(p1,p2);
        }
        gs[L][R] = ans;
        return ans;
    }

动态规划

动态规划和递归加缓存方式的区别就是,动态规划直接把缓存表先求出来,然后取值,在缓存表中拿,

代码演示

  /**
     * 动态规划
     * @param arr
     * @return
     */
    public static int dp(int[]arr){
        if (arr == null || arr.length == 0){
            return 0;
        }
        int N = arr.length;
        int[][]fs = new int[N][N];
        int[][]gs = new int[N][N];
        for (int i = 0; i < N ;i++){
            fs[i][i] = arr[i];
        }
        for (int i = 1; i < N ;i++){
            int L = 0;
            int R = i;
            while (R < N ){
            	//就是把递归方法换成从缓存表里拿,策略是一样的
                int p1 = arr[L] + gs[L + 1][R];
                int p2 = arr[R] + gs[L][R - 1];
                fs[L][R] = Math.max(p1,p2);
                int g1 =fs[L + 1][R];
                int g2= fs[L][R - 1];
                gs[L][R] = Math.min(g1,g2);
                L++;
                R++;

            }
        }
        return Math.max(fs[0][N - 1],gs[0][N - 1]);
    }

动态规划专题

爬楼梯问题-从暴力递归到动态规划

走到指定位置有多少种方式-从暴力递归到动态规划

零钱兑换,凑零钱问题,从暴力递归到动态规划

斐波那契数列-从暴力递归到动态规划文章来源地址https://www.toymoban.com/news/detail-533976.html

到了这里,关于纸牌博弈问题--动态规划(java)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Java数据结构与算法:动态规划之斐波那契数列

    大家好,我是免费搭建查券返利机器人赚佣金就用微赚淘客系统3.0的小编。在这寒冷的季节里,让我们一同探讨Java中的动态规划,重点关注解决问题的经典代表之一——斐波那契数列。 动态规划简介 动态规划是一种解决问题的数学方法,通常用于优化递归算法。它通过将问

    2024年01月22日
    浏览(47)
  • 数据结构与算法之美学习笔记:40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?

    本节课程思维导图: 淘宝的“双十一”购物节有各种促销活动,比如“满 200 元减 50 元”。假设你女朋友的购物车中有 n 个(n100)想买的商品,她希望从里面选几个,在凑够满减条件的前提下,让选出来的商品价格总和最大程度地接近满减条件(200 元),这样就可以极大限

    2024年02月03日
    浏览(47)
  • 【Java实现】动态规划算法解决01背包问题

    1、问题描述: 一个旅行者有一个最多能装m公斤的背包,现在有n中物品,每件的重量分别是W1、W2、……、Wn,每件物品的价值分别为C1、C2、……、Cn, 需要将物品放入背包中,要怎么样放才能保证背包中物品的总价值最大? 2、动态规划算法的概述 1)动态规划(Dynamic Progra

    2023年04月09日
    浏览(53)
  • 数据结构与算法之美学习笔记:41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题

    本节课程思维导图: 今天,我主要讲动态规划的一些理论知识。学完这节内容,可以帮你解决这样几个问题:什么样的问题可以用动态规划解决?解决动态规划问题的一般思考过程是什么样的?贪心、分治、回溯、动态规划这四种算法思想又有什么区别和联系? 什么样的问

    2024年02月02日
    浏览(64)
  • java实现0-1背包问题方案(动态规划-贪心算法-回溯-分支定界)

    动态规划算法时间复杂度较低,能够求解较大规模的问题,但空间复杂度较高,不适用于数据量较大的问题。 贪心算法时间复杂度较低,能够求解较大规模的问题,但不能保证求得的解是最优解。 回溯算法能够求解较小规模的问题,但时间复杂度较高,不适用于数据量较大

    2024年02月01日
    浏览(122)
  • 数据结构与算法-动态规划

    (我猜是做的多了背的题多了就自然懂了) 迭代法一般没有通用去重方式,因为已经相当于递归去重后了 这两个问题其实是一个问题,一般直接写出的没有去重的递归法,复杂度很高,此时需要使用备忘录去重,而备忘录去重时间复杂度和使用dp数组进行迭代求解时间复杂度相同

    2024年02月04日
    浏览(43)
  • 数据结构与算法 | 动态规划算法(Dynamic Programming)

    上一篇文末已经提到了记忆化搜索是动态规划(Dynamic Programming)的一种形式,是一种自顶向下(Top-Down)的思考方式,通常采用递归的编码形式;既然动态规划有自顶向下(Top-Down)的递归形式,自然想到对应的另外一种思考方式 自底向上( Bottom-Up ) ,也就是本篇要写的内

    2024年02月05日
    浏览(44)
  • python算法与数据结构---动态规划

    记不住过去的人,注定要重蹈覆辙。 对于一个模型为n的问题,将其分解为k个规模较小的子问题(阶段),按顺序求解子问题,前一子问题的解,为后一子问题提供有用的信息。在求解任一子问题时,通过决策求得局部最优解,依次解决各子问题。最后通过简单的判断,得到

    2024年02月20日
    浏览(65)
  • 数据结构与算法之贪心&动态规划

            一:思考         1.某天早上公司领导找你解决一个问题,明天公司有N个同等级的会议需要使用同一个会议室,现在给你这个N个会议的开始和结束 时间,你怎么样安排才能使会议室最大利用?即安排最多场次的会议?电影的话 那肯定是最多加票价最高的,入场

    2024年02月09日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包