【求助大神】NP-Hard，求无向图里最大和的算法，不是BFS/DFS这么简单，在线等

条件是这样的：

一个树/图，大概长这样子：
               3
             7   6
          2    4   9
        1    4    8   2

每个node的关系是：
例如 node, val=3，那么它和7和6 的 node互相指向对方.
3->7, 7->3
3->6, 6->3

然后就是每一层中间的node,都会分别指向上一层的它左边和右边的node。
例如第三层的 node, val =4, 它分别指向上一层的7和6。
那么第三层node 4就会分别有以下的关系：
4->7, 4->6,
4->4(第四层), 4->8.

最左和最右边的node都只指向一个上一层的node。例如第三层的node 2,它的关系有：
2->7,
2->1, 2->4（第四层）。

然后你会发现，每一层的node总数都比上一层多一个。。如此类推吧。。

里面的val不是sorted,有重复，并且像上面的形容那样，有cycle。。

希望大神们能够理解这个图的结构吧。

然后就是，写一个算法，要求能够在100层的图/树里面找到 sum 最大值，
要求的算法能够在 10秒内找到结果。

题意本身是说读取一份这样的文件，然后找到最大和。
所以前面还需要写I/O的程序，创造图的部分。这个都写了，感觉没有联系。。但如果有的话，请教一下怎么优化。。

我写了DFS，可是过不了，后面仔细分析一下的确不行，可是实在想不到怎么算才能够在10秒内实现。
所以说，这道题本身图小的话可以完成 (Polynomial)，图大的话就不行了(NP-Hard)。。

Dijisktra是求最短(小）的，不行。
Topological sorting是求DAG的，好像也不行。。

实在想不出来，在线等，谢谢大神们


补充内容 (2019-3-21 22:07):
补充一下这个例子的答案：3 +6+9+8 =26

补充内容 (2019-3-21 22:08):
忘记一个重要条件了：要求必须从最上面往下找，也就是root to leaves

ymsfnm4l 发表于 2019-3-21 22:53
杨辉三角了解一下 en.wikipedia.org/wiki/Pascal%27s_triangle

有一个原题我找不到了, 比较接近这个了
...

可是这个是找min path sum的，应该用不到吧？况且这个是graph,读取数据时我是一行一行读的，根本不知道grid size，每次reallocate grid size的话也会很慢，反正我想到是这些。。不如大神你用自己的话稍微解释一下？谢谢啦

这是一个比较经典的DP教学题，可以搜关键词 “动态规划 数塔”，有很多blog

magicsets 发表于 2019-3-22 01:23
这是一个比较经典的DP教学题，可以搜关键词 “动态规划 数塔”，有很多blog

太神奇了！我去研究一下，请大神多留意下我的问题哦谢谢啊

每个点连接下层的它的左右点。

1. 
   
2.                 3
   
3.               /   \
   
4.             4       5
   
5.           /   \   /   \
   
6.         10      6       9
   
7.       /   \   /   \   /   \
   
8.     8       5      -9      7
   

复制代码

从root出发，在每个点只可以向下走。走到底层。求路径中节点值的和最大。所以最大的路径应该是3 4 10 8 = 25

14417335 发表于 2019-3-22 08:21
每个点连接下层的它的左右点。
[mw_shl_code=bash,false]
                3

请问下你这贴想表达什么？

麻倉枼 发表于 2019-3-22 23:15
请问下你这贴想表达什么？

总结一下顶楼的描述。

14417335 发表于 2019-3-22 08:21
每个点连接下层的它的左右点。
[mw_shl_code=bash,false]
                3

谢谢啦，多了一个test case。