同一个子问题被计算多次,完全是没有必要的,可以缓存已经计算过的子问题,再次需要子问题结果时只需要从缓存中获取便可。这便是动态规划中的典型操作,优化重叠子问题,通过空间换时间的优化手段提高性能。...如拔河比赛中。如果 A队中的每一名成员的力气都是每一个班上最大的,由他们组成的拔河队毫无疑问,一定是也是所有拔河队中实力最强的。...显然,这很符合递归套路:递进给子问题,回溯子问题的结果。
使用二维数列表保存三角形数列中的所有数据。a=[[7],[3,8],[8,1,2],[2,7,4,4],[4,5,2,6,5]]。...:
[[4, 5, 2, 6, 5], [7, 12, 10, 10], [20, 13, 12], [23, 21], [30]]
'''
程序运行后,最终输出结果和前面手工绘制的dp表中的数据一模一样...上述解决问题时,使用了一个二维列表充当dp表,并保存所有的中间信息。
思考一下,真的有必要保存所有的中间信息吗?
在状态转移过程中,我们仅关心当前得到的状态信息,曾经的状态信息其实完全可以不用保存。