level 11
贪心算法
理论
贪心算法是一种在每一步选择当中都采取当前状态下好或优(即有利)的选择,从而希望导致结果是好或优的算法。
贪心算法在有优子结构的问题中尤为有效,简单地说,就是问题能够分解成子问题来解决,子问题的优解就能递推到终问题的优解。
细节
创建数学模型来描述问题;
把问题分成若干个子问题;
对每一子问题求解,得到子问题的局部优解;
把子问题的局部优解合并成原来问题的一个解。
2023年01月29日 05点01分
2
level 11
分治算法
理论
分治算法字面上的解释是“分而治之”,就是把一个复杂的问题拆分成两个或多个相同或相似的子问题,再把子问题拆分成更小的子问题......直到后子问题可以简单地求解,原问题的解即子问题的解的合并。
在广义的定义下,所有递归或循环的算法均被视为“分治算法”,也有只将具有少两个子问题的算法作为“分治算法”。
细节
在每一层递归上都有三个步骤:
分解:将原问题分解成若干个规模较小,相对独立,与原问题形式相同的子问题;
解决:若子问题规模较小且易于解决时,则直接解。否则,递归地解决各子问题;
合并:将各子问题的解合并为原问题的解。
2023年01月29日 05点01分
3