TopCoder SRM596: ColorfulRoad

dp[現在の位置] = 最小ステップ数として動的計画法を適用する

public class ColorfulRoad {
    public int getMin(string road) {
        int n = road.Length;
        int inf = 1 << 30;
        var dp = Enumerable.Repeat(inf, n).ToArray();
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if ("RGBR".Contains(road[j].ToString() + road[i].ToString())) {
                    dp[i] = Math.Min(dp[i], dp[j] + (i - j) * (i - j));
                }
            }
        }
        if (dp.Last() == inf) return -1;
        return dp.Last();
    }
}