Pythonで最初のプレイヤーが他のプレイヤーよりも多くのキャンディーを取ることができるかどうかを確認するプログラム

キャンディーと呼ばれる番号のリストがあり、2人が最も多くのキャンディーを集めるために競争しているとします。ここでは、レースはターンベースで、人1が最初に開始し、各ターンで、前または後ろからキャンディーを拾うことができます。人1が他の人よりも多くのキャンディーを集めることができるかどうかを確認する必要があります。

したがって、入力がキャンディー=[1、4、3、8]のようである場合、出力はTrueになります。これは、人1が最初のラウンドで8個のキャンディーを取ることができ、2人目が1または3を選ぶかどうかに関係なく、人1残りのキャンディーを取ることで勝つことができます。

これを解決するには、次の手順に従います-

• N：=キャンディーのサイズ

• 関数difference（）を定義します。これは左、右になります

• 左が右と同じ場合、

  • キャンディーを返す[左]

• （candies [left] − Difference（left + 1、right））と（candies [right] − Difference（left、right − 1））の最大値を返します

• メインメソッドから次のようにします-

• Difference（0、N − 1）> 0の場合はtrueを返し、それ以外の場合はfalseを返します

理解を深めるために、次の実装を見てみましょう-

例

class Solution:
   def solve(self, candies):
      N = len(candies)
      def difference(left, right):
         nonlocal candies
         if left == right:
            return candies[left]
         return max(candies[left] − difference(left + 1, right), candies[right] − difference(left, right − 1))
      return difference(0, N − 1) > 0
ob = Solution()
candies = [1, 4, 3, 8]
print(ob.solve(candies))

入力

[1, 4, 3, 8]

出力

True