King来写代码的专栏

回溯法分支限界法回溯法　　回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。 　　基本思想： 　　在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该

分治法动态规划贪心算法分治法　　分治法的基本思想是将一个规模为ｎ的问题分解为ｋ个规模较小的问题，这些子问题互相独立且与原问题相同（所以可以递归）。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。它的一般算法设计模式如下：divide-and-conquer(P){//|P|表示问题的规模，n0表示阈值，当规模不超过n0时，问题容易解出，不必分解 if(|P|<=n0)

这里讲两道题目（类型均是01背包类型的），两道题目均用了回溯法和动态规划两种解决办法，做了以后还是有所启发的。 　　第一道题目就是著名的01背包问题。 　　01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2……Wn，与之相对应的价值为P1,P2……Pn。求背包能放的最大价值。 　　回溯法的解法：//0-1背包问题，假定n为8（总共有8种物品），M=110（总共能放的

LeetCode动态规划归纳最近刷了很多动态规划的问题，归纳一下做动态规划的题的方法。动态规划很多题目是解决最多最少最大最小的问题。动态规划问题的基本做法是：确定递推量推出递推式确定边界在解决上述问题的同时，要时刻注意如何把全局的问题变成局部的（最优子结构），如何把前面计算过的子问题利用起来（重叠子问题）。下面把动态规划题分为几种类型。算种数的动态规划典型的题目包括：62.Unique Pa

算法与设计分析作业Divide and Conquerproblem-solving ideasPseudo-codeSubproblem reduction graphProve the correctnessDivide and Conquerproblem-solving ideasPseudo-codeSubproblem reduction graphProve the

算法与设计分析作业2动态规划Largest Divisible SubsetThe optimal substructure and DP equationPseudo-codeProve the correctnessThe complexity of your algorithmMoney robbingThe optimal substructure and DP equation

算法与设计分析作业3贪心Greedy AlgorithmPseudo-codeProve the correctnessThe complexity of your algorithmGreedy AlgorithmPseudo-codeProve the correctnessThe complexity of your algorithmProgrammingC Codeco