Tips: 如拔河比赛中。如果 A队中的每一名成员的力气都是每一个班上最大的,由他们组成的拔河队毫无疑问,一定是也是所有拔河队中实力最强的。...2.1 是否存在子问题
先来一个分治思想:思考或观察是否能把原始问题分解成相似的子问题,把解决问题的希望寄托在子问题上。
那么,针对上述三角形数列,是否存在子问题?...显然,这很符合递归套路:递进给子问题,回溯子问题的结果。
使用二维数列表保存三角形数列中的所有数据。a=[[7],[3,8],[8,1,2],[2,7,4,4],[4,5,2,6,5]]。...其实所有能套用动态规划的算法题,都可以使用递归实现,因递归平时接触多,从递归切入,可能更容易理解。
2.2 是否存在重叠子问题
先做一个实验,增加三角形数的行数,也就是延长路径线。...如下使用一个二维数组存储每一步的状态值。
有了上述的这张表,就可以使用动态规划自下向上的方式解决“兔子的难题”这个问题。