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)

では今日はこの辺で．
読んでいただいてありがとうございました😃