読者です 読者をやめる 読者になる 読者になる

本履歴

購入した古本の履歴と時々プログラミング

プログラムコンテストの練習問題

同じくAlgorithms and Programming: Problems and Solutionsより

一本道でn個の駅を持つ鉄道があり、i番目の駅からj番目の駅までの料金a[i,j]が与えられたとする時、1番目の駅からn番目の駅まで行く最小料金は?

dp[k]をk番目の駅からn番目の駅までにかかる最小料金とすると、
dp[n-1]=a[n-1,n]
dp[k]=min{a[k,n],a[k,k+1]+dp[k+2],a[k,k+2]+dp[k+3],...,a[k,k-2]+dp[k-1]}
を計算し、dp[1]が求めるもの。O(n^2)だな。