6. 多矩陣相乘運算次數

namespace Q6
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        private void textBox1_TextChanged(object sender, EventArgs e)
        {
            int n;
            if (!int.TryParse(textBox1.Text, out n)) return;
            label2.Text = $"請輸入m1~m{n}的矩陣大小<維度>:";

            panel1.Controls.Clear();
            for (int i = 0; i < n; i++)
            {
                var panel = new FlowLayoutPanel();
                panel.Width = panel1.Width;
                panel.Height = 25;
                var lbl = new Label();
                lbl.Text = $"m{i + 1}的矩陣大小: ";
                lbl.Width = 150;
                var tb1 = new TextBox();
                tb1.Width = 60;
                var tb2 = new TextBox();
                tb2.Width = 60;

                panel.Controls.Add(lbl);
                panel.Controls.Add(tb1);
                panel.Controls.Add(tb2);
                panel1.Controls.Add(panel);
            }
        }

        private void button1_Click(object sender, EventArgs e)
        {

        }

        private void button1_Click_1(object sender, EventArgs e)
        {
            var s = new List<int>();
            for (int i = 0; i < panel1.Controls.Count; i++)
            {
                var p = panel1.Controls[i];
                s.Add(int.Parse(p.Controls[1].Text));
                if (panel1.Controls.Count - 1 == i) s.Add(int.Parse(p.Controls[2].Text));
            }

            var n = s.Count - 1;
            var dp = new int[n + 1, n + 1];
            var sp = new int[n + 1, n + 1];

            for (int l = 2; l <= n; l++)
            {
                for (int i = 1; i <= n - l + 1; i++)
                {
                    int j = i + l - 1;

                    dp[i, j] = int.MaxValue;
                    for (int k = i; k < j; k++)
                    {
                        var cost = dp[i, k] + dp[k + 1, j] +
                            s[i - 1] * s[k] * s[j];
                        if (cost < dp[i, j])
                        {
                            dp[i, j] = cost;
                            sp[i, j] = k;
                        }
                    }
                }
            }


            label3.Text = $"矩陣相乘的次序為: {p(sp, 1, n)}\n最少的乘法運算次數: {dp[1, n]}";
        }

        string p(int[,] sp, int i, int j)
        {
            if (i == j) return $"m{i}";

            var k = sp[i, j];
            return $"<{p(sp, i, k)} {p(sp, k + 1, j)}>";
        }
    }
}

AST

var N = new int[] { 10, 100, 5, 50 };
List<string> print(int l, int r)
{
    if (l == r) return [$"m{l + 1}"];

    var result = new List<string>();
    for (int k = l; k < r; k++) // k is the split point
    {
        var left = print(l, k);
        var right = print(k + 1, r);

        foreach (var item in left)
        {
            foreach (var item1 in right)
            {
                result.Add($"<{item} {item1}>");
            }
        }
    }
    return result;
}

int calc(string s)
{

    List<string> tokens = new List<string>();
    var buffer = "";
    foreach (var item in s)
    {
        if (item == '<' || item == '>')
        {
            if (buffer.Length > 0)
            {
                tokens.Add(buffer);
                buffer = "";
            }
            tokens.Add(item.ToString());
            continue;
        }
        if (item == ' ')
        {
            if (buffer.Length > 0)
            {
                tokens.Add(buffer);
                buffer = "";
            }
            continue;
        }
        buffer += item;
    }
    if (buffer.Length > 0) tokens.Add(buffer);

    int idx = -1;
    string? peek()
    {
        if (idx + 1 >= tokens.Count) return null;
        return tokens[idx + 1];
    }
    //Console.WriteLine(string.Join(",", tokens));

    object build()
    {
        var token = peek();
        if (token == "<")
        {
            idx++;
            var left = build();
            var right = build();
            idx++;
            return (left, right);
        }
        idx++;
        return token;
    }

    int t = 0;
    (int, int) parse(object s)
    {
        if (s is string)
        {
            var z = int.Parse((s as string)[1..]);
            return (N[z - 1], N[z]);
        }
        var (l, r) = ((object, object))s;
        var lp = parse(l);
        var rp = parse(r);
        t += lp.Item1 * rp.Item1 * rp.Item2;
        return (lp.Item1, rp.Item2);
    }
    parse(build());
    return t;
}
int min = int.MaxValue;
string minStr = "";
foreach (var item in print(0, N.Length - 2))
{
    var k = calc(item);
    if (k < min)
    {
        min = k;
        minStr = item;
    }
}
Console.WriteLine(minStr);
Console.WriteLine(min);

D&C

var best = new int[N.Length - 1, N.Length - 1];
int daq(int l, int r)
{
    if (l == r)
        return 0;
    int k = int.MaxValue;
    var idx = -1;
    for (int i = l; i < r; i++)
    {
        int lcost = daq(l, i);
        int rcost = daq(i + 1, r);

        var cost = lcost + rcost + N[l] * N[i + 1] * N[r + 1];
        if (cost < k)
        {
            idx = i;
            k = Math.Min(k, cost);
        }
    }
    best[l, r] = idx;

    return k;
}

Console.WriteLine(daq(0, N.Length - 2));

string print(int l, int r)
{
    if (l == r) return $"m{l + 1}";

    var k = best[l, r];
    return $"<{print(l, k)} {print(k + 1, r)}>";
}
Console.WriteLine(print(0, N.Length - 2));