雑談スレ

91：名無しさん：2017/02/17(金) 01:25:59 ID:KHIvLZmI: 3次元を2次元に落とし込める理由は

入力側の頂点(k-1)を1度経由させる経路は
dp[k-1][i][k-1]もdp[k-1][k-1][j]もどちらも頂点(k-1)以降を経由しない(頂点0～(k-2)を経由する可能性のある)最短経路が保証され
2次元のdp[i][k-1]もdp[k-1][j]も同様のことが言える

更新される側の
2次元の場合、dp[i][j]が更新されていくわけで入力側に何らかの影響がありそうな雰囲気を感じることがあるのかもしれないけど
入力に影響がありそうに見えるのはこのiかjがどちらかが(k-1)だった場合、
つまり始点か終点が頂点(k-1)であり、それの最短経路の経由点に頂点(k-1)を含むことはないので入力に全く影響を与えない
3次元で言うと
dp[k][i][k-1]=min(dp[k-1][i][k-1],dp[k-1][i][k-1]+dp[k-1][k-1][k-1])これは常にdp[k][i][k-1]=dp[k-1][i][k-1] (どう見ても自明)
同様にdp[k][k-1][j]についてもいえる
i!=k-1かつj!=k-1のときはdp[k-1][][]からdp[k][][]への計算に再利用はされないから
3次元の最初の次元である使用する頂点の数というのを分けて考える必要ないから2次元に落とし込める

だめだ、俺も日本語下手だわ

新着レスの表示

※書き込む際の注意事項はこちら

※画像アップローダーはこちら

（画像を表示できるのは「画像リンクのサムネイル表示」がオンの掲示板に限ります）

掲示板管理者へ連絡無料レンタル掲示板