Pythonで同じ高さの隣接するツリーがない場合にツリーの高さを上げるための最小コストを見つけるプログラム

植物の高さを表す高さと呼ばれる数値のリストがあり、植物の高さを1つ増やすために必要な価格を表すコストと呼ばれる別の値のリストがあるとします。高さリストの各高さを隣接する高さと異なるものにするために、最小のコストを見つける必要があります。

したがって、入力が高さ=[3、2、2]コスト=[2、5、3]のようである場合、最後の高さを1増やすことができるため、出力は3になります。これは3です。

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

• 関数dp（）を定義します。これにはidx、l_height

  が必要です

• idxが高さのサイズと同じ-1の場合、

  • heights [idx]がl_heightと同じでない場合は、0を返します。それ以外の場合はcosts [idx]

• ret：=inf

• 0から2の範囲のiの場合、実行

  • heights [idx] + iがl_heightと同じでない場合、

    • ret：=retの最小値、dp（idx + 1、heights [idx] + i）+ cost [idx] * i

• retを返す

• メインメソッドからreturndp（0、null）

例

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

class Solution:
   def solve(self, heights, costs):
      def dp(idx, l_height):
         if idx == len(heights) - 1:
            return 0 if heights[idx] != l_height else costs[idx]
         ret = float("inf")
         for i in range(3):
            if heights[idx] + i != l_height:
               ret = min(ret, dp(idx + 1, heights[idx] + i) + costs[idx] * i)
         return ret
      return dp(0, None)
ob = Solution()
heights = [3, 2, 2]
costs = [2, 5, 3]
print(ob.solve(heights, costs))

入力

[3, 2, 2], [2, 5, 3]

出力

3