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

动态规划算法：

1. 初始化：将数塔的最后一行作为初始值。

2. 状态转移：从倒数第二行开始，依次计算每个结点的最大值。对于第i行第j列的结点，它的最大值为它下一行的第j和j+1列的结点的最大值加上它本身的值。

3. 最终结果：最终结果为数塔顶层结点的最大值。

Python代码实现：

import random
import time
import matplotlib.pyplot as plt

# 随机生成数塔
def generate_triangle(n):
    triangle = []
    for i in range(n):
        row = [random.randint(1, 100) for j in range(i+1)]
        triangle.append(row)
    return triangle

# 动态规划求解
def max_sum(triangle):
    n = len(triangle)
    dp = triangle[-1]
    for i in range(n-2, -1, -1):
        for j in range(i+1):
            dp[j] = max(dp[j], dp[j+1]) + triangle[i][j]
    return dp[0]

# 测试函数
def test(n):
    triangle = generate_triangle(n)
    start_time = time.time()
    result = max_sum(triangle)
    end_time = time.time()
    run_time = end_time - start_time
    print("n = %d, result = %d, run time = %f s" % (n, result, run_time))
    return run_time

# 画图函数
def plot(x, y):
    plt.plot(x, y)
    plt.title('Time vs N')
    plt.xlabel('N')
    plt.ylabel('Time (s)')
    plt.show()

if __name__ == '__main__':
    x = [4, 8, 16, 32, 64, 128]
    y = [test(n) for n in x]
    plot(x, y)

时间复杂度分析：

生成数塔的时间复杂度为O(N^2)，动态规划求解的时间复杂度为O(N^2)，因此总时间复杂度为O(N^2)