​ 算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。

​ 1、有穷性（Finiteness）：算法必须能在执行有限个步骤后终止。 ​ 2、确定性（Definiteness）：算法的每一步骤必须有确切的含义。 ​ 3、输入项（Input）：一个算法有零个或多个输入，这些输入取自某个特定的对象集合。 ​ 4、输出项（Output）：一个算法有一个或多个输出，以反映对输入数据加工后的结果。 ​ 5、可行性（Effectiveness）：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。

​ 1、自然语言 ​ 2、流程图 ​ 3、程序设计语言 ​ 4、伪代码

​ 常用的算法设计策略有：分治法、动态规划法、贪心法、回溯法、分支限界法、概率算法和近似算法等。

​ 算法分析技术的主要内容：正确性、可靠性、简单性、易理解性、时间复杂度和空间复杂度等。

分治法的基本思想：将一个难以直接解决的大问题，分解成一些规模较小的子问题，这些子问题相互独立且与原问题相同，然后各个击破，分而治之。

分治法常常与递归结合使用：通过反复应用分治，可以使子问题与原问题类型一致而规模不断缩小，最终使子问题缩小到很容易求出其解，由此自然导致递归算法。

人们从大量实践中发现，在使用分治法时，最好均匀划分。这种使子问题规模大致相等的做法源自一种平衡子问题的思想，它几乎总是比使子问题规模不等的做法好。

一般来说，分治算法在每一层递归上都有3个步骤。 (1) 分解。将原问题分解成一系列子问题。 (2) 求解。递归地求解各子问题。若子问题足够小，则直接求解。 (3) 合并。将子问题的解合并成原问题的解。

归并排序算法是成功应用分治法的一个完美的例子，其基本思想是将待排序元素分成大小大致相同的两个子序列，分别对这两个子序列进行排序，最终将排好序的子序列合并为所要求的序列。

归并排序算法完全依照上述分治算法的3个步骤进行。 (1) 分解。将n个元素分成各含n2个元素的子序列。 (2) 求解。用归并排序对两个子序列递归地排序。 (3) 合并。合并两个已经排好序的子序列以得到排序结果。

归并排序算法的C代码如下：

动态规划法的基本思想： 与分治法类似，也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合用动态规划法求解的问题，经分解得到的子问题往往不是独立的。若用分治法来解这类问题，则相同的子问题会被求解多次，以至于最后解决原问题需要耗费指数级时间。然而，不同子问题的数目常常只有多项式量级。如果能够保存已解决的子问题的答案，在需要时再找出已求得的答案，这样就可以避免大量的重复计算，从而得到多项式时间的算法。为了达到这个目的，可以用一个表来记录所有已解决的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解，每个解都对应于一个值，我们希望找到具有最优值(最大值或最小值)的那个解。当然，最优解可能会有多个，动态规划算法能找出其中的一个最优解。

设计一个动态规划算法，通常按照以下几个步骤进行。 (1) 找出最优解的性质，并刻画其结构特征。 (2) 递归地定义最优解的值。 (3) 以自底向上的方式计算出最优值。 (4) 根据计算最优值时得到的信息，构造一个最优解。 步骤(1) ~ (3)是动态规划算法的基本步骤。在只需要求出最优值的情形下，步骤(4)可以省略。 若需要求出问题的一个最优解，则必须执行步骤(4)。此时，在步骤(3)中计算最优值时，通常需记录更多的信息，以便在步骤(4)中根据所记录的信息快速构造出一个最优解。

对于一个给定的问题，若其具有以下两个性质，可以考虑用动态规划法来求解。 (1) 最优子结构。如果一个问题的最优解中包含了其子问题的最优解，就说该问题具有最优子结构。当一个问题具有最优子结构时，提示我们动态规划法可能会适用，但是此时贪心策略可能也是适用的。 (2) 重叠子问题。重叠子问题指用来解原问题的递归算法可反复地解同样的子问题，而不是总在产生新的子问题。即当一个递归算法不断地调用同一个问题时，就说该问题包含重叠子问题。此时若用分治法递归求解，则每次遇到子问题都会视为新问题，会极大地降低算法的效率，而动态规划法总是充分利用重叠子问题，对每个子问题仅计算一次，把解保存在一个在需要时就可以查看的表中，而每次查表的时间为常数。

有n个物品，第i个物品价值为 v i v_i vi​，重量为 w i w_i wi​，其中 v i v_i vi​和 w i w_i wi​均为非负数，背包的容量为W，W为非负数。现需要考虑如何选择装入背包的物品，使装入背包的物品总价值最大。

该问题可以形式化描述如下：目标函数为 m a x ∑ i = 1 n v i x i max\sum_{i=1}^{n}v_ix_i max∑i=1n​vi​xi​，约束条件为 ∑ i = 1 n w i x i ≤ W \sum_{i=1}^{n}w_ix_i≤W ∑i=1n​wi​xi​≤W ，满足约束条件的任一集合(x1, x2, …,xn)是问题的一个可行解，问题的目标是要求问题的一个最优解。

下面根据动态规划的4个步骤求解该问题：

(1) 刻画0-1背包问题的最优解的结构。可以将背包问题的求解过程看作是进行一系列的决策过程，即决定哪些物品应该放入背包，哪些物品不放入背包。如果一个问题的最优解包含了物品n，即 x n = 1 x_n=1 xn​=1，那么其余 x 1 x_1 x1​， x 2 x_2 x2​， x 3 x_3 x3​ … x n x_n xn​一定构成子问题1，2，3 … (n-1) 在容量为 W − w n W-w_n W−wn​时的最优解。如果这个最优解不包含物品n，即 x n = 0 x_n=0 xn​=0，那么其余 x 1 x_1 x1​， x 2 x_2 x2​， x 3 x_3 x3​ … x n x_n xn​一定构成子问题1，2，3 … (n-1) 在容量为 W 时的最优解。

(2) 递归定义最优解的值。根据上述分析的最优解的结构递归地定义问题最优解。设 c[i, w] 表示背包容量为 w 时 i 个物品导致的最优解的总价值，得到下式。显然，问题要求 c [ i , w ] = { 0 , i = 0 或 w = 0 c [ i − 1 , w ] , w i > w m a x { c [ i − 1 , w − w i ] + v i , c [ i − 1 , w ] } , i > 0 且 w i < w c[i,w]=\begin{cases}0 &,i=0或w=0\\c[i-1,w] &,w_i>w\\max\{c[i-1,w-w_i]+v_i,c[i-1,w]\}&,i>0且w_iw,i>0且wi​0或xi​=yj​,i,j>0或xi​=yj​​ (3) 计算最优解的值。 根据上述递归式自底向上地求出最优解的值。将 l [ i , j ] l[i,j] l[i,j]的值存储在表 l [ 1.. m , 1.. n ] l[1..m,1..n] l[1..m,1..n]中，以行为主序从左到右计算表 l l l中的元素，同时维持表 b [ 1.. m , 1.. n ] b[1..m,1..n] b[1..m,1..n]，用其中的元素 b [ i , j ] b[i,j] b[i,j]记录使得 l [ i , j ] l[i,j] l[i,j]取最优值的最优子结构。以下给出该算法的C代码，分别用strl和str2表示序列X和Y。