【Python】コーディング練習_2日目（LeetCode：Solving Questions With Brainpower）

はじめに

コーディング練習２日目です。

実装内容

一番大きな獲得ポイント値を返す。以下に詳細を記載する。

（例） 入力 = [[3, 2], [4, 3], [4, 4], [2, 5]]
配列の１つ目の数字は獲得ポイント、２つ目の数字はスキップ数を表している。
例えば、最初の組（[3, 2]）を選択した場合、獲得ポイントは３で、その後２つの組をスキップした後の配列（[2, 5]）に移動する。
ここで獲得できるポイントは２なので、出力は３＋２で５となる。
２つ目の組（[4, 3]）を選択した場合は、３つスキップした後に配列が存在しないので、獲得ポイント数は４。
同様に３つ目の組は４、４つ目の組は２となる。
この中で獲得ポイント数が最大のものは５なので、この値を出力する。

実装

Solving_Questions_With_Brainpower.py

from typing import List

class Solution:
    def mostPoints(self, questions: List[List[int]]) -> int:
        # ポイントとスキップ数の組の数
        n = len(questions)
        # 組の数の分だけ０を持つリストを作成
        dp = [0] * n
        # 作成したリストの末尾を、与えられた配列（question）の末尾の組の1つ目の値で置き換える。（ポイントのみを作成したリストに入れる）
        dp[-1] = questions[-1][0]
        # 0~2のインデックスについてもポイントを入れる（最後の組については、スキップできないため含めない）
        for i in range(n - 2, -1, -1):
            dp[i] = questions[i][0]
            skip = questions[i][1]
            if i + skip + 1 < n:
                dp[i] += dp[i + skip + 1]

            dp[i] = max(dp[i], dp[i + 1])
        return dp[0]

# テスト
if __name__ == "__main__":
    questions = [[3, 2], [4, 3], [4, 4], [2, 5]]
    print(Solution().mostPoints(questions))

参考