分治法

分治法：对于一个规模为n的问题，若该问题可以容易地解决则直接解决问题；否则将其分解为k各规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解决这些子问题，然后将各子问题的解，合并得到原问题的解。
步骤：分解（将原问题分解成一系列子问题）————求解（递归地求解各子问题，若子问题足够小，则直接求解） ————合并（将各子问题的解合并成原问题的解）。凡是涉及到分组解决的都是分治法(二分查找、归并排序、求阶乘、斐波那契数列等)。
递归：指子程序（函数）直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题合解决问题的常用方法。递归的两个基本要素：边界条件（确定递归何时终止，即递归出口）、递归模式（大问题如何分解成小问题，即递归体）

回溯法

回溯法（Backtracking）是一种选优的暴力搜寻法。但是，由于暴力，回溯法的时间复杂度较高，又称为试探法，
按优选条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通
就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为回溯点。

一般用于解决迷宫类的问题。其思路不难理解，想象一下你在走一个迷宫，当在一个路口有A,B,C三条岔路的时候你要怎么办呢？
大家可以很容易地想到先尝试道路A，如果走不通就回到这个路口尝试道路B，如果还走不通就尝试道路C，这就是一个典型地应用回溯法的例子。
如果将目光着眼于整个迷宫，就可以发现这个迷宫其实就是一颗多叉树，每个路口就是一个节点，每个路口的岔路就是这个节点的子树，
在这颗多叉树上应用深度优先搜索就是回溯法。

动态规划法

动态规划法（Dynamic Programming）：在求解问题中，对于每一步决策，列出各种可能的局部解，
通过决策保留那些有可能达到最优的局部解，丢弃其他局部解，以每一步都是最优解来保证全局是最优解。

本质也是将复杂的问题划分成一个个子问题，与分治法不同的是分治法中的每个子问题都是相同的，而动态规划法中的
每个子问题间不是互相独立的，并且不全都相同。

此算法会将大量经理放在前期构建表格上面，其会对每一步，列出各种可能的答案，这些答案会存储起来，最终要得出某个结果时，
是通过查询这张表来得到的。动态规划法不但每一步最优，全局也最优。

总结：动态规划法一定是具备了以下三个特点：

把原来的问题分解成了几个相似的子问题。（强调相似子问题）
所有的子问题都只需要解决一次。（强调只解决一次）
存储子问题的解。（强调存储）

贪心法

贪心法（Greedy）：总是做出在当前来说是最好的选择，而并不从整体上加以考虑，它所作的每步选择只是当前步骤的局部最优选择，
但从整体来说不一定是最优的选择。由于它不比为了寻找最优解而穷尽所有可能解，因此其耗费时间少，一般可以快速得到满意的解，但得不到最优解。

局部贪心，只针对当前的步骤取最优，而非整体考虑。

判断此类算法，就看算法是否每一步都取最优，并且整体题意没有透露出最终结果是最优的。

例子

例子：找零钱问题
假设我们有面值为 1 元、5 元、11 元的硬币，现在需要凑出 15 元，目标是使用最少数量的硬币。

贪心法的策略
贪心法的每一步都选择当前最优的局部解，即尽可能使用面值最大的硬币。
步骤：
选择 11 元硬币，剩余金额为15 − 11 = 4 元。
选择 1 元硬币，剩余金额为4 − 1 = 3 元。
选择 1 元硬币，剩余金额为3 − 1 = 2 元。
选择 1 元硬币，剩余金额为2 − 1 = 1 元。
选择 1 元硬币，剩余金额为1 − 1 = 0 元。
结果：使用了 5 枚硬币（11 + 1 + 1 + 1 + 1）。
问题：贪心法没有达到全局最优解。实际上，使用 3 枚硬币（5 + 5 + 5）就可以凑出 15 元。

动态规划法的策略
动态规划法会考虑所有可能的组合，找到全局最优解。

状态定义： dp[i] 表示凑出金额 i 所需的最少硬币数。
状态转移方程：
dp[ i ] = min ⁡(dp[i − 1], dp[i − 5], dp[i − 11])+ 1
其中 dp[i − 1]、 dp[i − 5]、 dp[i − 11] 分别表示使用 1 元、5 元、11 元硬币后的最少硬币数。
初始化： dp[ 0 ]=0（凑出 0 元需要 0 枚硬币），其他 dp[i]= ∞ 。
计算过程： dp[1]= dp[0]+ 1 = 1
dp[2]= dp[1]+ 1 = 2
dp[3]= dp[2]+ 1 = 3
dp[4]= dp[3]+ 1 = 4
dp[5]= min ⁡(dp[4], dp[0])+ 1 = 1
dp[6]= min ⁡(dp[5], dp[1])+ 1 = 2
dp[7]= min ⁡(dp[6], dp[2])+ 1 = 3
dp[8]= min ⁡(dp[7], dp[3])+ 1 = 4
dp[9]= min ⁡(dp[8], dp[4])+ 1 = 5
dp[10]= min ⁡(dp[9], dp[5])+ 1 = 2
dp[11]= min ⁡(dp[10], dp[6], dp[0])+ 1 = 1
dp[12]= min ⁡(dp[11], dp[7], dp[1])+ 1 = 2
dp[13]= min ⁡(dp[12], dp[8], dp[2])+ 1 = 3
dp[14]= min ⁡(dp[13], dp[9], dp[3])+ 1 = 4
dp[15]= min ⁡(dp[14], dp[10], dp[4])+ 1 = 3
结果： dp[15]= 3 ，即使用 3 枚硬币（5 + 5 + 5）。

对比总结
贪心法：

当前最优：每一步选择面值最大的硬币。
结果：使用了 5 枚硬币（11 + 1 + 1 + 1 + 1）。
问题：没有达到全局最优。

动态规划法：

全局最优：考虑所有可能的组合，找到最少硬币数。
结果：使用了 3 枚硬币（5 + 5 + 5）。

为什么动态规划法是全局最优？
动态规划法通过穷举所有可能的子问题，并利用记忆化存储子问题的解，从而确保找到全局最优解。
它不会像贪心法那样只关注当前最优，而是综合考虑所有可能的路径。

为什么贪心法是当前最优？
贪心法每一步都选择当前最优的局部解，但没有考虑未来的影响。因此，贪心法可能会错过全局最优解，尤其是在问题具有复杂依赖关系时。

适用场景

动态规划法：适合具有重叠子问题和最优子结构的问题，如背包问题、最长公共子序列等。
贪心法：适合问题具有贪心选择性质，即局部最优能导致全局最优，如最小生成树、哈夫曼编码等。

public class CoinChangeDP {

    // 动态规划法解决找零钱问题
    public static int coinChangeDP(int[] coins, int amount) {
        // dp[i] 表示凑出金额 i 所需的最少硬币数
        int[] dp = new int[amount + 1];

        // 初始化 dp 数组，初始值为无穷大（表示无法凑出）
        for (int i = 1; i <= amount; i++) {
            dp[i] = Integer.MAX_VALUE;
        }

        // 凑出 0 元需要 0 枚硬币
        dp[0] = 0;

        // 动态规划填充 dp 数组
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i >= coin && dp[i - coin] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        // 如果 dp[amount] 仍然是无穷大，说明无法凑出
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        int[] coins = {1, 5, 11}; // 硬币面值
        int amount = 16; // 目标金额
        int result = coinChangeDP(coins, amount);
        System.out.println("动态规划法 - 最少硬币数: " + result);
    }
}

public class CoinChangeGreedy {

    // 贪心法解决找零钱问题
    public static int coinChangeGreedy(int[] coins, int amount) {
        // 将硬币面值从大到小排序
        Arrays.sort(coins);
        reverseArray(coins);

        int count = 0; // 记录硬币数量
        int remaining = amount; // 剩余金额

        // 贪心地选择面值最大的硬币
        for (int coin : coins) {
            while (remaining >= coin) {
                remaining -= coin;
                count++;
            }
            if (remaining == 0) {
                break;
            }
        }

        // 如果剩余金额不为 0，说明无法凑出
        return remaining == 0 ? count : -1;
    }

    // 辅助方法：反转数组
    private static void reverseArray(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }

    public static void main(String[] args) {
        int[] coins = {1, 5, 11}; // 硬币面值
        int amount = 16; // 目标金额
        int result = coinChangeGreedy(coins, amount);
        System.out.println("贪心法 - 最少硬币数: " + result);
    }
}

分支界限法

分支界限法：与回溯法类似，同样是在问题的解空间树上搜索问题解的一种算法，它常以广度优先或以最小耗费（最大收益）优先的方式搜索问题的解空间树。

举个例子，假设你要去旅行，需要选择一些物品装进行李箱。你希望选择的物品总价值最大，但行李箱的容量有限。你可以使用分支限定法来解决这个问题。

首先，你需要确定每个物品的价值和重量。然后，你可以创建一个分支界限法的搜索树，每个节点代表一种可能的物品选择方案。在搜索树中，每个节点都有两种可能的分支：选择或不选择该物品。

接下来，你可以计算每个节点的价值和重量，并选择价值最大的分支进行扩展。这个过程会一直持续，直到直到一个可行的物品选择方案，或者搜索树中的所有分支都被扩展完毕。

在这个例子中，分支界限法通过有限考虑价值最大的物品来快速找到最优的物品选择方案。这种方法可以避免盲目搜索解空间树，从而提高算法效率。

回溯法和分支界限法的区别

回溯法
- 求解目标：回溯法的求解目标是找出解空间中满足约束条件的一个解或所有解。
- 搜索方式深度优先：回溯法会搜索整个解空间，当不满条件时，丢弃，继续搜索下一个儿子节点，如果所有儿子节点都不满足，向上回溯到它的父节点。
分支界限法
- 求解目标：分支界限法的目标一般是在满足约束条件的解中找出在某种意义下的最优解，也有找出满足约束条件的一个解
- 搜索方式：分支界限法以广度优先或以最小损耗优先的方式搜索解空间

概率算法

概率算法：常见类型算法例如分治法、贪心算法、动态规划、回溯法和分支界限法基本都属于确定性算法。即每一计算步骤都是确定的，而且在最后一定会返回一个确定的解。
概率算法允许算法在每一步的执行过程中都可以随机的选择下一个计算步骤，所以在最后不一定能得到解。概率算法的一个重要特征就是，
对所求解的同一实例使用同一算法求解多次，其结果可能是不同的，而且求解的时间也可能会有较大的差异。