Topic
- pythonで動的計画法の緩和のchminを実装する.
chminの実装方法
C++で実装すると...
template<class T> void chmin(T& a, T b){
if (a > b){
a = b;
}
}
これを自力で,pythonに直してみる.
def chmin(a,b):
if a > b :
a = b
うまくいかない.
多分,参照型がうまくいってないのかもしれない.
(原因がわからないので,わかる方はコメントお願いします)
色々漁ってたどり着いた方法がこちら↓
def chmin(dp,i,x):
if dp[i] > x:
dp[i] = x
つまり,dpも渡してしまおう作戦.dp渡してiで配列のインデックスを指定する感じ.
問題解決能力を鍛える! アルゴリズムとデータ構造のCode5.3をpythonで書き換えるとこんな感じ.
def chmin(dp,i,x):
if dp[i] > x:
dp[i] = x
n = int(input())
h = list(map(int,input().split()))
dp = [float("inf")]*len(h)
dp[0] = 0
for i in range(1,len(h)):
chmin(dp,i, dp[i-1]+abs(h[i]-h[i-1]))
if i > 1:
chmin(dp,i,dp[i-2]+abs(h[i]-h[i-2]))
print(dp)
では今日はこの辺で.
読んでいただいてありがとうございました😃