python一线开发 [2021]最佳路径算法与状态转移方程与三角形最大路径问题 做游戏的动态巡路用 ```python # 状态转移方程: 最佳路径(i, j) = 目标数组(i, j) + max{最佳路径(i + 1, j), 最佳路径(i + 1, j + 1)}。 def walk_array(pArray): saved_path = [] saved_array = pArray[-1] # 最佳路径要倒叙 for i in range(len(pArray)-2, -1, -1): # 从底往上 # 更改dp前j个的值 save_path_num = 0 for j in range(i+1): max_num = max(saved_array[j], saved_array[j+1]) saved_array[j] = pArray[i][j] + max_num save_path_num = pArray[i][j] saved_path.append(save_path_num) return (saved_array[0], saved_path) ``` ```python (max_num, saved_path) = walk_array(triangle_array) print('最大值: {}, 路径:'.format(max_num)) for item in range(len(saved_path)-1, -1, -1): print("{}->".format(saved_path[item])) ``` ```python triangle_array = [ [7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5] ] ``` 时间复杂度n2 阅读全文 2021-04-05 huoji 0 条评论
