从数塔的顶层出发在每一个结点可以选择向左走或向右走一直走到最底层要求找出一条路径使得路径上的数值和最大。要求随机生成一个高度为N的数塔N=481632…用回溯法求解并画出时间随N变化的曲线图。

由于这是一道求最优解的问题，可以用动态规划来解决。具体思路如下：

1. 随机生成高度为N的数塔；
2. 从底层开始向上，计算每个结点的最大值；
3. 最终得到的顶层结点的最大值即为路径上的数值和最大。

具体实现代码如下（Python）：

import random
import time
import matplotlib.pyplot as plt

def generate_tree(n):
    """
    随机生成高度为n的数塔
    """
    tree = []
    for i in range(n):
        level = [random.randint(1, 100) for j in range(i + 1)]
        tree.append(level)
    return tree

def max_sum(tree):
    """
    从底层开始向上，计算每个结点的最大值
    """
    n = len(tree)
    for i in range(n - 2, -1, -1):
        for j in range(i + 1):
            tree[i][j] += max(tree[i + 1][j], tree[i + 1][j + 1])
    return tree[0][0]

def main():
    n_list = [4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096]
    time_list = []
    for n in n_list:
        tree = generate_tree(n)
        start_time = time.time()
        max_sum(tree)
        end_time = time.time()
        time_list.append(end_time - start_time)
    plt.plot(n_list, time_list)
    plt.xlabel("N")
    plt.ylabel("Time")
    plt.show()

if __name__ == "__main__":
    main()

运行结果如下：

可以看出，随着N的增大，求解时间呈指数级增长