NeetCode 150 [1-D Dynamic Programming]:easy

NeetCodeのSolutionを書いていく

Climbing Stairs

整数nが与えられます。
nは階段の段数です。
階段は1段か2段(1段飛ばし)上がれます。
階段を登るステップのユニーク数を返してください。

時間：O(n)
メモリ：O(n)

1か2しか無い。

• 2段の場合は2パターン
  • 1,1
  • 2
• 3段の場合は3パターン
  • 1,1,1
  • 1,2
  • 2,1
• 4段の場合は5パターン
  • 1,1,1,1
  • 2,1,1
  • 1,2,1
  • 1,1,2
  • 2,2
• 5段の場合は8パターン
  • 1,1,1,1,1
  • 2,1,1,1
  • 1,2,1,1
  • 1,1,2,1
  • 1,1,1,2
  • 2,2,1
  • 2,1,2
  • 1,2,2
• 6段の場合は13パターン
  • 1,1,1,1,1,1
  • 2,1,1,1,1
  • 1,2,1,1,1
  • 1,1,2,1,1
  • 1,1,1,2,1
  • 1,1,1,1,2
  • 2,2,1,1
  • 2,1,2,1
  • 2,1,1,2
  • 1,2,2,1
  • 1,2,1,2
  • 1,1,2,2
  • 2,2,2

残り3段から残り2段に移動するパターンは1パターンなのでパターンが1つ増える。
残り2段からのパターン数(2)+1=3
残り4段からの場合は残り3段へ、1段飛ばしで2段目にも行けるので
残り3段からのパターン数(3)+残り2段からのパターン数(2)=5
残り5段からの場合は残り4段へ、1段飛ばしで3段目にも行けるので
残り4段からのパターン数(5)+残り3段からのパターン3=8
残り6段からの・・・

1つ前と2つ前の段のパターンを足せば良い。
これでいいのかな？ループの回数はnだし、リストのサイズもn。

class Solution:
    def climbStairs(self, n: int) -> int:
        result = 0
        number = []
        number.append(1)
        number.append(2)
        if n == 1:
            return 1
        if n == 2:
            return 2

        for i in range(2,n):
            number.append(number[i-1] + number[i-2])
        return number[-1]

いけた！

Min Cost Climbing Stairs

最小のコストで階段を登る。
cost[i]は階段のステップに登録されたコストであり、そのコストを払うことで次のステップに進める。
最初のステップは0か1を選択できる。
階段の頂上(最後のindexを超える)に移動する最小コストを返せ。

推奨コスト
計算：O(n)
メモリ：O(n)

今回はステップごとに掛かるコストが違うので解析的なアルゴリズムでは答えが出なさそうか？
とはいえ計算はO(n)なので行けるはずか。

下からそれぞれのステップに至る最小コストを積み上げていけばいいか？
n段目の最小コストを出す場合には「n-1+n-1段目のコスト」と「n-2+n-2段目のコスト」を比較して小さい方を選ぶ。

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        def mymin(one, two, idx):
            idx += 1
            if idx == 0:
                one = cost[0]
                return mymin(one, two, idx)
            elif idx == 1:
                two = cost[1]
                return mymin(one, two, idx)

            if idx >= (len(cost)):
                return min(one,two)

            temp1 = one + cost[idx]
            temp2 = two + cost[idx]
            one = two
            two = min(temp1, temp2)

            return mymin(one, two, idx)

        return mymin(0,0,-1)

いけた！
けど結構ややこしいな。
もっといい方法がありそう。

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        for i in range(len(cost) - 3, -1, -1):
            cost[i] += min(cost[i + 1], cost[i + 2])

        return min(cost[0], cost[1])

これでいけるのか。すげー。
なるほど。