746.最小費用で階段を登る(Python)
1614 ワード
タイトル
難易度:★☆☆☆タイプ:配列、ダイナミックプランニング
配列の各インデックスは1つのステップとし,i番目のステップは非負数の体力費値costiに対応する.
階段を登るたびに、対応する体力費値を費やし、階段を登り続けるか、2つの階段を登るかを選択することができます.
フロアの上部に達する最低コストを見つける必要があります.最初は、インデックスが0または1の要素から初期ステップとして選択できます.
注意costの長さは[2,1000]になります.各cost[i]は[0,999]の範囲のIntegerタイプになります.
例1入力:cost=[10,15,20]出力:15解釈:最低コストはcost[1]から始まり、2歩歩くと階段の頂上に着き、合計15かかります.
例2入力:cost=[1,100,1,1,1,100,1,1,100,1,1,100,1]出力:6解釈:最低コスト方式はcost[0]から始まり、それら1を1つずつ通過し、costをスキップ[3]、合計6を費やす.
に答える
私たちは動的計画でこの問題を解決します.
まず特殊な状況を考慮して、入力ステップ配列が空の場合、ゼロを返し、入力問題配列が2つの要素を超えない場合、その中の最小値を返す.
配列dpを定義し,dp[i]は,iと表記された階段に到達するために消費される最小エネルギーを表す.ここで注意しなければならないのは、上部階段が実際にテーマにデフォルトで設定されていることです.すなわち、上部階段に到達するために消費されるエネルギーはゼロであり、補完する必要があります.
条件は一度に1歩か2歩歩ける.
i=0を初期化すると、1つのステップしかないので、そのステップの上部に到達するために必要なエネルギーは、そのステップに到達するために必要なエネルギーでありcost[0]である.i=1の場合、2つの階段があり、私たちは2歩歩いて、第1段の階段を飛び越えることができ、この階段に到達するのに必要なエネルギーは第2段の階段に到達するために必要なエネルギーであり、cost[1].
状態遷移方程式i>1の場合、i段目に到達するには2つの選択肢しかなく、1つはi-1段目から1歩、もう1つはi-2段目から2歩、この2つの選択で消費される最小エネルギーはそれぞれdp[i-1]+cost[i]とdp[i-2]+cost[i]であり、両者の最小値、すなわちiと表記された段に到達するために必要な最小エネルギー:dp[i]=min(dp[i-1],dp[i-2])+cost[i]である.
エンコーディングの実装:
質問やアドバイスがあれば、コメントエリアへようこそ~
難易度:★☆☆☆タイプ:配列、ダイナミックプランニング
配列の各インデックスは1つのステップとし,i番目のステップは非負数の体力費値costiに対応する.
階段を登るたびに、対応する体力費値を費やし、階段を登り続けるか、2つの階段を登るかを選択することができます.
フロアの上部に達する最低コストを見つける必要があります.最初は、インデックスが0または1の要素から初期ステップとして選択できます.
注意costの長さは[2,1000]になります.各cost[i]は[0,999]の範囲のIntegerタイプになります.
例1入力:cost=[10,15,20]出力:15解釈:最低コストはcost[1]から始まり、2歩歩くと階段の頂上に着き、合計15かかります.
例2入力:cost=[1,100,1,1,1,100,1,1,100,1,1,100,1]出力:6解釈:最低コスト方式はcost[0]から始まり、それら1を1つずつ通過し、costをスキップ[3]、合計6を費やす.
に答える
私たちは動的計画でこの問題を解決します.
まず特殊な状況を考慮して、入力ステップ配列が空の場合、ゼロを返し、入力問題配列が2つの要素を超えない場合、その中の最小値を返す.
配列dpを定義し,dp[i]は,iと表記された階段に到達するために消費される最小エネルギーを表す.ここで注意しなければならないのは、上部階段が実際にテーマにデフォルトで設定されていることです.すなわち、上部階段に到達するために消費されるエネルギーはゼロであり、補完する必要があります.
条件は一度に1歩か2歩歩ける.
i=0を初期化すると、1つのステップしかないので、そのステップの上部に到達するために必要なエネルギーは、そのステップに到達するために必要なエネルギーでありcost[0]である.i=1の場合、2つの階段があり、私たちは2歩歩いて、第1段の階段を飛び越えることができ、この階段に到達するのに必要なエネルギーは第2段の階段に到達するために必要なエネルギーであり、cost[1].
状態遷移方程式i>1の場合、i段目に到達するには2つの選択肢しかなく、1つはi-1段目から1歩、もう1つはi-2段目から2歩、この2つの選択で消費される最小エネルギーはそれぞれdp[i-1]+cost[i]とdp[i-2]+cost[i]であり、両者の最小値、すなわちiと表記された段に到達するために必要な最小エネルギー:dp[i]=min(dp[i-1],dp[i-2])+cost[i]である.
エンコーディングの実装:
class Solution:
def minCostClimbingStairs(self, cost):
if not cost:
return 0
if len(cost) <= 2:
return min(cost)
cost.append(0)
dp = [None for _ in range(len(cost))]
dp[0], dp[1] = cost[0], cost[1]
for i in range(2, len(cost)):
dp[i] = min(dp[i-2], dp[i-1]) + cost[i]
print(dp)
return dp[-1]
質問やアドバイスがあれば、コメントエリアへようこそ~