本人对于这两种算法有个拙见,望各位指点一二。
本人认为最暴力的动态规划其实并不需要满足无后效性,也就是用很多维来表示出所有的状态。但是实际上解决问题时后效性也是使用动态规划的一个必要条件。本人认为这个原因有可能是因为贪心夹入了动态规划。更准确地说,我认为这是用贪心优化了动态规划的时间与空间,因而导致了动态规划需要满足无后效性。
望各位讲解一下这个想法的对错,以此加上我的理解与印象。希望各位讨论时尽量语气温和,关爱菜鸡笔者。