c# - 最大路径总和在带质数校验的三角形中

Question

我得到了这个算法任务:

您将在下面输入一个三角形，您需要根据下面给定的规则找到数字的最大总和；

1. 您将从顶部开始，向下移动到下图中的相邻编号。
2. 你只能向下和斜着走。

3. 您只能走过非质数。

        1
       8 4
     2  6  9
    8  5  9  3
   

如您所见，它有几条符合非素数规则的路径； 1>8>6>9, 1>4>6>9, 1>4>9>91 + 8 + 6 + 9 = 24。如您所见，1、8、6、9 都不是质数，遍历这些数会得出最大和。

根据上述规则，以下输入的最大总和是多少？这意味着请将这个金字塔作为您的实现的输入(作为文件或直接在代码中的常量)并使用它来解决。

                                  215
                               193 124
                             117 237 442
                           218 935 347 235
                         320 804 522 417 345
                       229 601 723 835 133 124
                     248 202 277 433 207 263 257
                   359 464 504 528 516 716 871 182
                 461 441 426 656 863 560 380 171 923
               381 348 573 533 447 632 387 176 975 449
             223 711 445 645 245 543 931 532 937 541 444
           330 131 333 928 377 733 017 778 839 168 197 197
        131 171 522 137 217 224 291 413 528 520 227 229 928
      223 626 034 683 839 053 627 310 713 999 629 817 410 121
    924 622 911 233 325 139 721 218 253 223 107 233 230 124 233

请注意，每个节点在这里只有两个子节点(最底部的节点除外)。例如，您可以从 215 走到 124(因为 193 是素数)，然后从 124 走到 237 或 442。您不能从 124 走到 117，因为它不是 124 的直接子节点。

我知道有不同的方法可以解决这个问题

• 蛮力法

• 动态规划法

我使用动态规划方法是因为它的效率:

using System;

class Program
{
    static void Main(string[] args)
    {


        //get input
        var input = GetInput();

        string[] arrayOfRowsByNewlines = input.Split('\n');

        var tableHolder = FlattenTheTriangleIntoTable(arrayOfRowsByNewlines);

        var result = WalkThroughTheNode(arrayOfRowsByNewlines, tableHolder);

        Console.WriteLine($"The Maximum Total Sum Of Non-Prime Numbers From Top To Bottom Is:  {result[0,0]}");

        Console.ReadKey();
    }

    private static string GetInput()
    {

            const string input = @"   215
                                   193 124
                                  117 237 442
                                218 935 347 235
                              320 804 522 417 345
                            229 601 723 835 133 124
                          248 202 277 433 207 263 257
                        359 464 504 528 516 716 871 182
                      461 441 426 656 863 560 380 171 923
                     381 348 573 533 447 632 387 176 975 449
                   223 711 445 645 245 543 931 532 937 541 444
                 330 131 333 928 377 733 017 778 839 168 197 197
                131 171 522 137 217 224 291 413 528 520 227 229 928
              223 626 034 683 839 053 627 310 713 999 629 817 410 121
            924 622 911 233 325 139 721 218 253 223 107 233 230 124 233";
        return input;
    }

    private static int[,] WalkThroughTheNode(string[] arrayOfRowsByNewlines, int[,] tableHolder)
    {
        // walking through the non-prime node
        for (int i = arrayOfRowsByNewlines.Length - 2; i >= 0; i--)
        {
            for (int j = 0; j < arrayOfRowsByNewlines.Length; j++)
            {
                //only sum through the non-prime node
                if ((!IsPrime(tableHolder[i, j])))
                {
                    tableHolder[i, j] = Math.Max(tableHolder[i, j] + tableHolder[i + 1, j],
                        tableHolder[i, j] + tableHolder[i + 1, j + 1]);
                }
            }
        }
        return tableHolder;
    }

    private static int[,] FlattenTheTriangleIntoTable(string[] arrayOfRowsByNewlines)
    {
        int[,] tableHolder = new int[arrayOfRowsByNewlines.Length, arrayOfRowsByNewlines.Length + 1];

        for (int row = 0; row < arrayOfRowsByNewlines.Length; row++)
        {
            var eachCharactersInRow = arrayOfRowsByNewlines[row].Trim().Split(' ');

            for (int column = 0; column < eachCharactersInRow.Length; column++)
            {
                int number;
                int.TryParse(eachCharactersInRow[column], out number);
                tableHolder[row, column] = number;
            }
        }
        return tableHolder;
    }

    public static bool IsPrime(int number)
    {
        // Test whether the parameter is a prime number.
        if ((number & 1) == 0)
        {
            if (number == 2)
            {
                return true;
            }
            return false;
        }

        for (int i = 3; (i * i) <= number; i += 2)
        {
            if ((number % i) == 0)
            {
                return false;
            }
        }
        return number != 1;
    }




}

谁能帮我检查一下代码，看看是否有更好的解决方法。

Answer 1

素数检查效率不高，但对于如此小的数字来说并不重要。您的动态规划方法很好，但是素数的逻辑存在错误。您只检查父节点是否为质数。因此，如果两个 child 都是素数，则父节点永远不会成为有效路径的一部分，但如果父节点不是素数，您仍然会提升两个素数中较大的一个 + 父值。如何修复:

1. 在最低级别:如果一个数是质数，则将其设置为 -1。

2. 在下一级:如果数字是质数或两个 child 都 < 0，则将其设置为 -1，否则像以前一样取数字 + child 的最大值。

3. 如果顶部节点的值为 -1，则没有到底部的有效路径，否则它是最大路径的总和不踩素数。