常用解题的方法有穷举法，分治法，动态规划法，贪心法，回溯法，

1.穷举法

穷举法就是一个不漏的测试所有的可能结果是否符合要求，也称为蛮力法，暴力破解法，是求解问题的规模较小时最直接的解题方法。但求解问题规模较大时，难度较大，数据结构较复杂时，无法穷举问题的所有解，或者时间超时。

如：查找数组中是否指定元素；

 public  Boolean qingju(int [] arr,int  target){  
        for (int i = 0; i < arr.length; i++) {
            if(arr[i]==target){
                return  true;
            }
        }
        return false;
    }

时间复杂度为O(n)，把所有元素都操作一遍

2.分治法

分治法（Divide  and  Conquer）采用分而治之，逐个解决的策略。采用分治法求解的问题必须具有两个性质：

1. 最优子结构，指一个问题可以分为若干个规模较小的子问题，各子问题与原问题类型相同；问题的规模缩小到一定程度能够直接解决；该问题的解包含着其子问题的解，将子问题的解合并最终能够得到原问题的解
2. 子问题独立，指问题所分解的子问题是相互独立的，没有重叠部分。

分支法将一个难以解决的大问题分解成若干个规模较小的子问题，子问题与原问题类型相同，则求解算法相同，递推解决子问题到可解的最小规模，分别求解子问题，再将子问题的解合并成一个规模较大子规模的解，从而自底向上地逐步求解得到原问题的解。因此，分治法可以用递归算法表示。常用于：遍历树，二分法查找，快速排序

采用分治的递归算法描述如下：

结果  求解问题  （问题规模）
{
    if（问题规模足够小）                     //边界条件
       求解小规模子问题；                    //直接解决问题，没有递归调用
    else                   
        whlie（存在子问题）                 //递归条件      
            求解问题（子问题规模）；         //递归调用，分解成若干个子问题
    return   各子问题合并后的解；
}

实例：快速排序

效率分析：

分治法将一个问题分解成数目较少的多个子问题，如果每次划分各子问题的规模近乎相等，则分治策略效率高。

如：顺序查找，划分子序列长度分别为0和n-1时，将问题规模缩小了1，时间复杂度为O(n)

      二分查找，每次选择序列中间位置进行比较，为了获取两个长度相等的子序列将问题规模缩小了一半，时间复杂度为O（log2n）

3.动态规划法

动态规划法（Dynamic  Programming）求解问题必须具备两个性质：

1. 最优子结构
2. 子问题重叠，指解决问题的子问题不是相互独立的，有重叠部分。

动态规划法采用备忘录解决子问题重叠。对每个子问题只求解一次，保存每个子问题的计算结果，就像一个备忘录当需要再次求解某个子问题时，只需要查找备忘录的结果即可，要求备忘录查询时间为 常数。

实例：存储杨辉三角

    public int [][] CombinationNumber (int n){
        int [][]yanghui=new int[n+1][];  //创建一个n+1行的杨辉三角
        for (int i = 0; i <yanghui.length ; i++) {
            yanghui[i]=new int[i+1];    //每行申请i+1个元素的一维数组
            yanghui[i][0]=yanghui[i][i]=1;  //每行首尾为1
            for (int j = 0; j <i ; j++) {
                yanghui[i][j]=yanghui[i-1][j-1]+yanghui[i-1][j]; 
              //第i行j列元素为其上一行（i-1）的前两个元素（j-1，j）的和
            }
        }
        return   yanghui;
    }

4.贪心法

贪心法（Greedy）是运用局部最优选择以期获得全局最优解的一种策略，用于求解极值（最大值/最小值）问题。采用贪心算法求解的问题必须具备两个性质；

1. 最优子结构
2. 贪心选择：求解问题最优解时，贪心法将最优子结构问题的求解过程分为若干步骤，每一步在当前状态下做出最好选择

实例：小明拿着100元去买东西，买了7块钱东西，售货员小姐姐找了他一堆零钱，求小明手里最少有多少张钱币？

 注： 钱币种类分100元，50元，20元，10元，5元，2元，1元

 //money为小明拿的钱，value商品花的钱，返回找到纸币数
public   int  findMoney(int money ,int value){ 

        int n=money-value;
        if(n<0){         //若钱不够返回-1
            return  -1;
        }
        int count=0;
        while(n>0){      //当找钱时先和金额大纸币的纸币比较
            if(n>50){
                count++;
                n-=50;
            }else  if(n>20){
                count++;
                n-=20;
            }else  if(n>10){
                count++;
                n-=10;
            }else  if(n>5){
                count++;
                n-=5;
            }else  if(n>2){
                count++;
                n-=2;
            }else  if(n>=1){
                count++;
                n-=1;
            }

        }
        return  count;
    }

    贪心法总是做出当前看来最好的选择，换言之，贪心法并不从整体最优考虑，它所作出的选择在某种意义上是局部的最优选择，期望得到的最终结果也是整体最优的。虽然贪心法不能对所有问题都得到整体最优解，但对许多问题它都能得到整体最优解，如最小生成树，或者得到的结果是最优解的很好近似。

小结：分治法，动态规划法和贪心法都具有最优子结构性质。分治法，动态规划法的原问题依赖各自问题的解，只有在求出子问题的解后，才能得到原问题的解，分解问题的过程都是自顶向下的，求解过程却是自底向上的，和递归调用与返回过程一致。贪心法则仅是在当前状态下做出局部的最优选择，然后再去解决其后产生的子问题，依赖于所做过的选择，不依赖子问题的解。因此，求解问题过程是自顶向下的，每次贪心选择将所求问题简化为规模更小的子问题，经过若干迭代，最终得到最优解。

最后

以上就是斯文水池为你收集整理的数据结构的几种解题法1.穷举法2.分治法3.动态规划法4.贪心法的全部内容，希望文章能够帮你解决数据结构的几种解题法1.穷举法2.分治法3.动态规划法4.贪心法所遇到的程序开发问题。

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