你要明白自顶向下是一个递归的过程,原始问题会分解成两个子问题,对于子问题继续递归求解。而备忘录法的实质就是"每次计算后,我们会把计算结果保存在表格中",那么当我们遇到一个子问题,我们可以先在表格查找这个子问题是否存在(伪代码的第一句if F[i][j]<0),如果不存在就计算这个子问题,如果存在,F[i][j]里存的就是这个子问题的解,直接跳转到最后一行return F[i][j]。然后考虑这个自顶而下的过程F[4][5]需要求解F[3][3]和F[3][5],这两个子问题继续递归下去,你发现,只有F[1][2]这个子问题,需要求解两遍,第一遍继续求解子问题,第二遍查找!而这次查找也带来了效率的提升,随着表格的表大,查找的比例会更大
点赞 6

相关推荐

牛客网
牛客企业服务