足跡-sokuseki-

りかの日進月歩の記録

AOJ1277 Minimal Backgammon

Minimal Backgammon | Aizu Online Judge

問題概要

0から  N までのマスがあるすごろくをします。マスには何も書いていないマス、止まると1ターン休みになるマス、止まるとスタートのマスまで戻るマスがあります。マス0がスタートのマス、マス  N がゴールのマスで、どちらのマスにも何も書いてありません。
6面のサイコロを使って駒を動かします。駒はゴールのマスより先に進めないので、例えば  N-3 のマスにいるときにサイコロの目が5のとき、駒は N-2 に進みます。
 T ターン以内に駒がゴールに到達する確率を求めてください。

制約

 5 \le N \le 100
 1 \le T \le 100

解法

dp[  i ][  j ] :=  i ターン目にマス j にいる確率
として確率DPをします

AIZU ONLINE JUDGE: Code Review