动态规划中三角数塔问题(python版本）

本文主要是介绍动态规划中三角数塔问题(python版本），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

###python版本
import numpy as np
class triangle_dynatic():def main(self,data):#data塔的原始数据，dp存储动态数据dp = np.zeros(np.array(data).shape)#n为行数，在这里相当于塔数n,m = np.array(data).shape#初始化dp#下面这个循环相当于把data的最后一行付给了dp的最后一行，就是从最后一行向上递归for i in range(n):dp[n-1][i] = data[n-1][i]print(dp)#第一个循环从最底层往上，第二层循环从左向右，在这里从第四层，就是倒数第二层开始向上进行动态规划for i in range(n-2,-1,-1):for j in range(i+1):temp_max = max(dp[i+1][j],dp[i+1][j+1])dp[i][j] = temp_max+data[i][j]#打印最终结果print('最大的路径和为：\n%d'%dp[0][0])#首先输出塔顶元素print('最大路径：\n->%d'%data[0][0])j = 0#依次输出2/3/4/5层的所选路径for i in range(1,n):node_value = dp[i-1][j]-data[i-1][j]#如果node_value == dp[i][j]则说明下一步应该是data[i][j]；如果node_value == dp[i][j + 1]则说明下一步应该是data[i][j + 1]if node_value == dp[i][j+1]:j = j+1print('->%d'%data[i][j])data = [[9,0,0,0,0],[12,15,0,0,0],[10,6,8,0,0],[2,18,9,5,0],[19,7,10,4,16]]triangle_dynatic().main(data)

这篇关于动态规划中三角数塔问题(python版本）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---