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

Question

我得到了这个算法任务：

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

您将从顶部开始，向下移动到相邻的编号，如下所示。
只允许向下和斜着走。
你只能走过非质数。
```
     1
    8 4
  2  6  9
 8  5  9  3
```

如您所见，这有几条路径符合非素数规则； 1>8>6>9, 1>4>6>9, 1>4>9>9 1 + 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

注意，这里每个节点只有两个children（最下面的除外）。例如，您可以从 215 走到 124（因为 193 是质数），然后从 124 走到 237 或 442。从 124 不能走到 117，因为它不是 124 的直接 child。

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

蛮力法
动态规划法

由于效率高，我使用了动态规划方法：

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

素数检查效率不高，但对于这么小的数字来说并不重要。您的动态规划方法很好，但是素数的逻辑存在错误。您只检查 parent 节点是否为素数。因此，如果两个 children 都是质数，则 parent 节点永远不会成为有效路径的一部分，但如果 parent 不是质数。如何解决：

在最低层：如果一个数是质数，则将其设置为-1。
在下一级：如果数字是质数或两个 children 都小于 0，则将其设置为 -1 否则将数字 + children 的最大值作为之前.
如果顶部节点的值为-1，则没有到底部的有效路径，否则它是最大路径的总和不踩素数。

Answer 2

这对我有用

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

internal static class Program
{
    /// <summary>
    /// </summary>
    public static Dictionary<int, bool> PrimeCache = new Dictionary<int, bool>();

    private static void Main(string[] args)
    {
        var result = GetInput()
            .TransformInputToArray()
            .TransformTo2Darray()
            .ResetAllPrimeNumbers()
            .WalkThroughTheNode();

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

    /// <summary>
    ///     Prepare input
    /// </summary>
    /// <returns></returns>
    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;
    }

    /// <summary>
    ///     Transform the input to array
    /// </summary>
    /// <param name="input"></param>
    /// <returns></returns>
    private static string[] TransformInputToArray(this string input)
    {
        return input.Split(new[] {Environment.NewLine}, StringSplitOptions.RemoveEmptyEntries);
    }

    /// <summary>
    ///     Transform the array to 2D array
    /// </summary>
    /// <param name="arrayOfRowsByNewlines"></param>
    /// <returns></returns>
    private static int[,] TransformTo2Darray(this string[] arrayOfRowsByNewlines)
    {
        var tableHolder = new int[arrayOfRowsByNewlines.Length, arrayOfRowsByNewlines.Length + 1];

        for (var row = 0; row < arrayOfRowsByNewlines.Length; row++)
        {
            var eachCharactersInRow = arrayOfRowsByNewlines[row].ExtractNumber();

            for (var column = 0; column < eachCharactersInRow.Length; column++)
                tableHolder[row, column] = eachCharactersInRow[column];
        }
        return tableHolder;
    }

    /// <summary>
    ///     Extract Number from the row
    /// </summary>
    /// <param name="rows"></param>
    /// <returns></returns>
    private static int[] ExtractNumber(this string rows)
    {
        return
            Regex
                .Matches(rows, "[0-9]+")
                .Cast<Match>()
                .Select(m => int.Parse(m.Value)).ToArray();
    }

    /// <summary>
    ///     Reset all the prime number to zero
    /// </summary>
    /// <param name="tableHolder"></param>
    /// <returns></returns>
    private static int[,] ResetAllPrimeNumbers(this int[,] tableHolder)
    {
        var length = tableHolder.GetLength(0);
        for (var i = 0; i < length; i++)
        {
            for (var j = 0; j < length; j++)
            {
                if (tableHolder[i, j] == 0) continue;
                if (IsPrime(tableHolder[i, j]))
                    tableHolder[i, j] = 0;
            }
        }
        return tableHolder;
    }

    /// <summary>
    ///     Walk through all the non prime
    /// </summary>
    /// <param name="tableHolder"></param>
    /// <returns></returns>
    private static int WalkThroughTheNode(this int[,] tableHolder)
    {
        var tempresult = tableHolder;
        var length = tableHolder.GetLength(0);

        // walking through the non-prime node

        for (var i = length - 2; i >= 0; i--)
        {
            for (var j = 0; j < length; j++)
            {
                var c = tempresult[i, j];
                var a = tempresult[i + 1, j];
                var b = tempresult[i + 1, j + 1];
                if ((!IsPrime(c) && !IsPrime(a)) || (!IsPrime(c) && !IsPrime(b)))
                    tableHolder[i, j] = c + Math.Max(a, b);
            }
        }
        return tableHolder[0, 0];
    }

    /// <summary>
    ///     prime number check
    /// </summary>
    /// <param name="number"></param>
    /// <returns></returns>
    public static bool IsPrime(this int number)
    {
        // Test whether the parameter is a prime number.
        if (PrimeCache.ContainsKey(number))
        {
            bool value;
            PrimeCache.TryGetValue(number, out value);
            return value;
        }
        if ((number & 1) == 0)
        {
            if (number == 2)
            {
                if (!PrimeCache.ContainsKey(number)) PrimeCache.Add(number, true);
                return true;
            }
            if (!PrimeCache.ContainsKey(number)) PrimeCache.Add(number, false);
            return false;
        }

        for (var i = 3; i*i <= number; i += 2)
        {
            if (number%i == 0)
            {
                if (!PrimeCache.ContainsKey(number)) PrimeCache.Add(number, false);
                return false;
            }
        }
        var check = number != 1;
        if (!PrimeCache.ContainsKey(number)) PrimeCache.Add(number, check);
        return check;
    }
}

Answer 3

我在 Java 中尝试了以下解决方案：

// Creating 2 dimensional array with the input triangle
int[][] data = Files.lines(Paths.get("E:\Personal\triangle2.txt"))
        .map(s -> stream(s.trim().split("\s+")).mapToInt(Integer::parseInt).toArray()).toArray(int[][]::new);

int[][] originalData = Files.lines(Paths.get("E:\Personal\triangle2.txt"))
        .map(s -> stream(s.trim().split("\s+")).mapToInt(Integer::parseInt).toArray()).toArray(int[][]::new);

/*
 * Below would be code flow if we didnt had to consider skipping the
 * prime numbers.
 * for (int lengthIndex = data.length - 1; lengthIndex >  0; lengthIndex--)
 *   for (int i = 0; i < data[lengthIndex].length - 1;  i++)
 *       data[lengthIndex - 1][i] += Math.max(data[lengthIndex][i],data[lengthIndex][i + 1]);
 */

// Using the bottom-up approach starting from the lowermost node to upwards
for (int lengthIndex = data.length - 1; lengthIndex > 0; lengthIndex--)
    for (int i = 0; i < data[lengthIndex].length - 1; i++) {
        System.out.println("lenghtindex is" + lengthIndex);
        if(!checkPrimeOnOriginalArray(data[lengthIndex - 1][i]) || (lengthIndex == 1)) {
            System.out.println("gettign here");
            data[lengthIndex - 1][i] += Math.max(
                    data[lengthIndex][i],data[lengthIndex][i + 1]);
            System.out.println("-->"+data[lengthIndex - 1][i]);
        }
        else {
            data[lengthIndex - 1][i] = 0;
        }
    }

//data[lengthIndex - 1][i] += Math.max(
//      checkPrimeOnOriginalArray(originalData[lengthIndex][i]) ? 0 : data[lengthIndex][i],
//      checkPrimeOnOriginalArray(originalData[lengthIndex][i + 1]) ? 0 : data[lengthIndex][i + 1]);

System.out.println("Maximum Sum Of Path Is : "+data[0][0]);

Answer 4

对于这个具体问题，你的方法似乎很合理。这个问题是一个更普遍的问题的简化版本；您可能会考虑解决更普遍的问题。

构造一个有向图，其中节点是三角形的元素，有向边从一个节点到可以到达的节点。
创建一个开始节点，边到三角形的顶部，和一个停止节点，边从每个底部节点到它。
删除所有到达素数节点的边。
一条边的权重是它指向的节点的负值；停止节点的值为零。
现在你有一个加权有向无环图。使用标准的最小路径查找算法找到从开始节点到停止节点的最小成本路径。
最低成本是您要查找的值的负数。

此技术适用于任何带权有向无环图，而不仅仅是三角形。

Answer 5

你不觉得它没有检查最后一行的质数检查并取最大值吗？

代码应该如下所示：

for (int lenIndex = data.length - 1; lenIndex > 0; lenIndex--) {
        for (int i = 0; i < data[lenIndex].length - 1; i++) {
            System.out.println("---------------------");
            System.out.println("lenIndex is : " + lenIndex);
            if (!isPrimeNum(data[lenIndex - 1][i]) || (lenIndex == 1)) {
                if (lenIndex == data.length - 1) {
                    data[lenIndex - 1][i] += Math.max(isPrimeNum(data[lenIndex][i]) ? 0 : data[lenIndex][i],
                            isPrimeNum(data[lenIndex][i + 1]) ? 0 : data[lenIndex][i + 1]);

                    System.out.println("data[lenIndex][i] : " + data[lenIndex][i]+ " data[lenIndex][i + 1] :"+ data[lenIndex][i + 1]);
                    System.out.println("Number select for Sum #" + Math.max(isPrimeNum(data[lenIndex][i]) ? 0 : data[lenIndex][i],
                            isPrimeNum(data[lenIndex][i + 1]) ? 0 : data[lenIndex][i + 1]));
                } else {
                    data[lenIndex - 1][i] += Math.max(data[lenIndex][i], data[lenIndex][i + 1]);
                    System.out.println("data[lenIndex][i] : " + data[lenIndex][i]+ " data[lenIndex][i + 1] :"+ data[lenIndex][i + 1]);
                    System.out.println("Number select for Sum #" + Math.max(data[lenIndex][i], data[lenIndex][i + 1]));
                }
                System.out.println("Afrer Sum #" + data[lenIndex - 1][i]);
            } else {
                System.out.println("Prime Number - Skiping : " + data[lenIndex - 1][i]);
                data[lenIndex - 1][i] = 0;
            }
        }

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

Maximum path sum In a triangle with prime number check

c#

algorithm

primes