而贪心算法任务无需求解所有子问题,所以选择在当前情况下最优的情况自顶向下的求解问题,贪心可以认为是动态规划的一个特例
如果用一个树来表示子问题的话 可以认为动态规划考虑了树中的所有节点
而贪心算法减去了树了许多枝干...也就是说,上述数组中,3 0.5 8这3个数的乘积30.58=12是最大的,而且是连续的。...把这种操作需要的次数定义为两个字符串的距离 L, 则相似度定义为1/(L+1) 即距离加一的倒数。...那么jackbllog和jackblog的相似度为 1/1+1=1/2=0.5 也就是所两个字符串的相似度是 0.5。
给定任意两个字符串,你是否写出一个是否来计算出它们的相识度。...5、最长公共子序列
对于序列S和T,求它们的最长公共子序列。例如X={A,B,C,B,D,A,B},Y={B,D,C,A,B,A}则它们的lcs是{B,C,B,A}和{B,D,A,B}。