Codingame『Bender - The Money Machine』クリア

Bender / José Carlos Cortizo Pérez

　普通に再帰で全探索したら時間が足りなくてアウト。
そこで初めて動的計画法を考えてみた。
動的計画法 - Wikipedia

　いやぁ凄いね。スイスイですよ、スイスイ。
かかる時間が雲泥の差。
それでもイマイチ理解しきれてない感があるんですよね。

using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/
class Solution
{
    //部屋
    public static Room[] rooms;
    //最大取得金額
    public static int maxMoney;

    static void Main(string[] args)
    {
        //部屋数get
        int N = int.Parse(Console.ReadLine());
        rooms = new Room[N];
        Console.Error.WriteLine(N);

        //部屋のデータget set
        for (int i = 0; i < N; i++)
        {
            string[] r = Console.ReadLine().Split(' ');
            int roomNum = int.Parse(r[0]);
            rooms[roomNum] = new Room();
            //rooms[roomNum].isVisit = false;
            rooms[roomNum].memo = 0;
            rooms[roomNum].Money = int.Parse(r[1]);
            rooms[roomNum].next = new int[2];
            if (r[2] == "E") rooms[roomNum].next[0] = -1;
            else rooms[roomNum].next[0] = int.Parse(r[2]);
            if (r[3] == "E") rooms[roomNum].next[1] = -1;
            else rooms[roomNum].next[1] = int.Parse(r[3]);
            Console.Error.WriteLine(String.Format("{0} {1} {2} {3}", roomNum, rooms[roomNum].Money, rooms[roomNum].next[0], rooms[roomNum].next[1]));
        }

        // Write an action using Console.WriteLine()
        // To debug: Console.Error.WriteLine("Debug messages...");

        //sercher(0, 0);
        sercherDP();

        Console.WriteLine(maxMoney);
    }

    //多分動的計画とかいうアレ
    static void sercherDP()
    {
        //最大金額初期化
        maxMoney = 0;
        //最初のメモに最初の部屋の金額を書き込む
        rooms[0].memo = rooms[0].Money;

        for (int i = 0; i < rooms.Length; i++)
        {
            for (int j = 0; j < rooms[i].next.Length; j++)
            {
                //次の部屋が出口でなければ
                if (rooms[i].next[j] != -1)
                {
                    //次の部屋のメモに、今の部屋のメモ金額＋次の部屋の金を書きに行く
                    int tmp = rooms[i].memo + rooms[rooms[i].next[j]].Money;
                    //既にメモが書いてあったら、金額を見て多い方に更新する
                    if (rooms[rooms[i].next[j]].memo < tmp)
                    {
                        rooms[rooms[i].next[j]].memo = tmp;
                    }
                    //Console.Error.WriteLine(String.Format("{0} : {1}", rooms[i].next[j], rooms[rooms[i].next[j]].memo)); 
                    //RoomState();
                }
                else
                {
                    //メモが最大金額より大きかったら更新
                    if (maxMoney < rooms[i].memo)
                    {
                        maxMoney = rooms[i].memo;
                    }
                }
            }
        }
    }

    /*
    //部屋状態
    static void RoomState()
    {
        Console.Error.WriteLine("+++++++");
        for(int i = 0; i < rooms.Length; i++) {
            Console.Error.WriteLine(String.Format("{0} {1} {2} {3} {4}", i, rooms[i].Money, rooms[i].memo, rooms[i].next[0], rooms[i].next[1]));             
        }
    }
    */

    /*
    static void sercher(int n, int m)
    {
        m += rooms[n].Money;
        
        //Find exit
        if(rooms[n].next[0] == -1 | rooms[n].next[1] == -1) {
            if(maxMoney < m) maxMoney = m;
        }
        
        //move next door 1
        if(rooms[n].next[0] != -1) {
            if(rooms[rooms[n].next[0]].isVisit != true) {
                rooms[n].isVisit = true;
                sercher(rooms[n].next[0], m);
            }
        }
        //move next door 2
        if(rooms[n].next[1] != -1) {
            if(rooms[rooms[n].next[1]].isVisit != true) {
                rooms[n].isVisit = true;
                sercher(rooms[n].next[1], m);
            }
        }

        rooms[n].isVisit = false;        
        return;
    }
    */

    //部屋クラス
    public class Room
    {
        //通過フラグ
        //public bool isVisit;
        //金額メモ
        public int memo;
        //落ちてる金
        public int Money;
        //次の部屋の番号
        public int[] next;
    }
}