欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  互联网

石子游戏

程序员文章站 2022-06-23 09:45:11
一、题目描述题目链接:https://leetcode-cn.com/problems/stone-game/二、题目分析可以使用搜索的方法来解决。对于每次操作,都有两个选择,拿最左边的石堆或者拿最右边的石堆,剩下的可以到下一层递归,而且这里是可以使用memo优化的,因为先拿左边再拿右边,和先拿右边再拿左边是等价的。三、代码 private Integer[][] memo; public boolean stoneGame(int[] piles) {.....

一、题目描述

题目链接:https://leetcode-cn.com/problems/stone-game/

石子游戏

 

二、题目分析

可以使用搜索的方法来解决。对于每次操作,都有两个选择,拿最左边的石堆或者拿最右边的石堆,剩下的可以到下一层递归,而且这里是可以使用memo优化的,因为先拿左边再拿右边,和先拿右边再拿左边是等价的。

 

三、代码

    private Integer[][] memo;
    public boolean stoneGame(int[] piles) {
        memo = new Integer[piles.length][piles.length];
        int sum = 0;
        for (int num: piles) {
            sum += num;
        }
        int res = stoneHelper(piles,0,piles.length-1);
        return res > (sum - res);
    }

    private int stoneHelper(int[] piles, int left, int right) {
        if (left == right) return piles[left];
        if (memo[left][right] != null) return memo[left][right];
        int pickLeft = piles[left] + stoneHelper(piles,left+1,right);
        int pickRight = piles[right] + stoneHelper(piles,left,right-1);
        return memo[left][right] = Math.max(pickLeft,pickRight);
    }

 

本文地址:https://blog.csdn.net/ykben/article/details/107313816