一、动态规划

算法实现的步骤

1、创建一个一维数组或者二维数组，保存每一个子问题的结果，具体创建一维数组还是二维数组看题目而定，基本上如果题目中给出的是一个一维数组进行操作，就可以只创建一个一维数组，如果题目中给出了两个一维数组进行操作或者两种不同类型的变量值，比如背包问题中的不同物体的体积与总体积，找零钱问题中的不同面值零钱与总钱数，这样就需要创建一个二维数组。

注：需要创建二维数组的解法，都可以创建一个一维数组运用滚动数组的方式来解决，即一位数组中的值不停的变化，后面会详细徐叙述

2、设置数组边界值，一维数组就是设置第一个数字，二维数组就是设置第一行跟第一列的值，特别的滚动一维数组是要设置整个数组的值，然后根据后面不同的数据加进来变幻成不同的值。

3、找出状态转换方程，也就是说找到每个状态跟他上一个状态的关系，根据状态转化方程写出代码。

4、返回需要的值，一般是数组的最后一个或者二维数组的最右下角。

代码基本框架：

for(j=1; j<=m; j=j+1) // 第一个阶段
    xn[j] = 初始值;
 
for(i=n-1; i>=1; i=i-1)// 其他n-1个阶段
    for(j=1; j>=f(i); j=j+1)//f(i)与i有关的表达式
      xi[j]=j=max（或min）{g(xi-[j1:j2]), ......, g(xi-1[jk:jk+1])};
 
 t = g(x1[j1:j2]); // 由子问题的最优解求解整个问题的最优解的方案
 
 print(x1[j1]);
 
 for(i=2; i<=n-1; i=i+1）
 {  
      t = t-xi-1[ji];
 
      for(j=1; j>=f(i); j=j+1)
         if(t=xi[ji])
              break;}

例子

1. 斐波那契
2. 数组最大不连续递增子序列
3. 数组最大连续子序列和
4. 数字塔从上到下所有路径中和最大的路径
5. 两个字符串最大公共子序列
6. 背包问题
7. 找零钱问题：有几种方法
8. 找零钱问题：所用面额数量最少
9. 最长重复子数组
10. 最大回文子串

二、排序算法

几种常用排序算法

三、KMP算法

KMP算法

四、贪心算法

例子

旅行家的预算

五、图论算法

克鲁斯卡尔算法

最后

以上就是聪明鼠标为你收集整理的算法学习总结一、动态规划二、排序算法三、KMP算法四、贪心算法五、图论算法的全部内容，希望文章能够帮你解决算法学习总结一、动态规划二、排序算法三、KMP算法四、贪心算法五、图论算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。