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

Project Euler 18

Problem 18

DP の練習。

  • new 演算子で配列を生成すると、その要素は規定値で初期化される。
    • たとえば int の配列の場合は 0 で初期化される。
  • Linq 少しずつ慣れてきた。
    • map は Select
    • filter は Where
    • reduce は Aggregate
  • int.Parse で文字列から整数へ変換。
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class PE018 {
    static int Calc(List<List<int>> table) {
        int n = table.Count;

        int[,] dp = new int[n, n];
        dp[0, 0] = table[0][0];
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                int a = j > 0 ? dp[i-1, j-1] : 0;
                int b = dp[i-1, j];
                dp[i, j] = table[i][j] + Math.Max(a, b);
            }
        }
        return Enumerable.Range(0, n).Select(i => dp[n-1, i]).Max();
    }

    static void Main() {
        var table = new List<List<int>>();

        foreach (string s in File.ReadAllLines("../data/18.txt")) {
            var xs = new List<int>();
            string[] ds = s.Trim().Split(new char[] { ' ' });
            foreach (string t in ds) {
                xs.Add(int.Parse(t));
            }
            table.Add(xs);
        }

        Console.WriteLine(Calc(table));
    }
}

18.txt は以下です。

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

参考: