TopCoder SRM 150 DIV 1 Medium 練習

問題

あるキャンバスに縦のストライプを塗る。ストライプの柄が与えられるので、最小で何回キャンバスに描けば模様が完成するか。

解

俺の嫁ですとも。ええ。動的計画法です。

using System;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections;
using System.Collections.Generic;

public class StripePainter {
    int[,] dp = new int[50, 50];
    string str;
    public int minStrokes(string stripes)
    {
        str = stripes;
        for (int i = 0; i < 50; ++i)
            for (int j = 0; j < 50; ++j)
                dp[i, j] = -1;
        return rec(0, str.Length - 1);
    }

    private int rec(int p, int q)
    {
        if (p > q)
            return 0;
        if (p < 0 || q < 0 || p >= str.Length || q >= str.Length)
            return 9999;
        if(dp[p, q] > 0)
            return dp[p, q];
        if(p == q)
            return 1;
        dp[p, q] = 9999;
        for (int i = p; i < q; ++i)
            dp[p, q] = Math.Min(dp[p, q], rec(p, i) + rec(i + 1, q) - (str[p] == str[q] ? 1 : 0));
        return dp[p, q];
    }
}