如何设计算法

分而治之

动态规划

贪婪算法

回溯算法

结论

在研究和设计算法的过程中，我最喜欢的部分之一就是观察程序员解决问题时采用的不同方法。在本文中，我将讨论一些可用于解决问题的常用技术，例如……

分治算法
动态规划
贪婪算法
回溯算法

分而治之

在我关于排序算法的文章中，我们研究了归并排序和快速排序算法。两者的共同点在于它们都是分而治之的算法。分而治之是一种常见的算法设计方法，它涉及将问题分解为与原始问题类似的较小子问题。它通常以递归方式解决子问题，并将子问题的解组合起来以解决原始问题。

分而治之方法的逻辑可以分为三个步骤：

将原始问题分解为更小的子问题。
通过使用递归算法解决子问题并返回子问题的解决方案来解决子问题。
将子问题的解决方案组合成原问题的解决方案。

分治法示例：二分查找

在我上一篇关于搜索算法的文章中，我们使用迭代方法实现了二分查找。这里我们将使用分治法来实现二分查找。

function binarySearchRecursive(array, value, low, high) {
    if (low <= high) {
        const mid = Math.floor((low + high) / 2);
        const element = array[mid];

        if (element < value) {
            return binarySearchRecursive(array, value, mid + 1, high);
        } else if (element > value) {
            return binarySearchRecursive(array, value, low, mid - 1);
        } else {
            return mid;
        }
    }
    return null;
}

export function binarySearch(array, value) {
    const sortedArray = quickSort(array);
    const low = 0;
    const high = sortedArray.length - 1;

    return binarySearchRecursive(array, value, low, high);
}

请注意，binarySearch上面的函数是开发人员看到的执行搜索的函数，也是binarySearchRecursive我们使用分而治之方法的地方。

动态规划

动态规划是一种优化技术，用于通过将复杂问题分解为更小的子问题来解决。这听起来很像分而治之的方法，但动态规划不是将问题分解为独立的子问题，然后再合并，而是将问题分解为相互依赖的子问题。

逻辑可以分为三个步骤：

定义子问题。
实现解决子问题的递归。
识别并解决基本情况。

动态规划示例：最小硬币找零问题

这个问题是一道常见面试题“硬币找零”的变体。硬币找零问题是指用给定数量的面值硬币，找出有多少种方法可以找零特定数量的美分。最小硬币找零问题是指用给定数量的面值硬币，找出需要多少枚硬币才能凑成特定数量的美分。例如，如果你需要找零 39 美分，你可以使用 1 枚 25 美分硬币、1 枚 10 美分硬币和 4 枚 1 美分硬币。

function minCoinChange(coins, amount) {
    const cache = [];
    const makeChange = (value) => {
        if (!value) {
            return [];
        }
        if (cache[value]) {
            return cache[value];
        }
        let min = [];
        let newMin;
        let newAmount;
        for (let i = 0; i < coins.length; i++) {
            const coin = coins[i];
            newAmount = value - coin;
            if (newAmount >= 0) {
                newMin = makeChange(newAmount);
            }
            if (newAmount >= 0 && 
            (newMin.length < min.length - 1 || !min.length) && (newMin.length || !newAmount)) {
                min = [coin].concat(newMin);
            }
        }
        return (cache[value] = min);
    }
    return makeChange(amount);
}

关于上述实现的一些注意事项：coins参数代表面额（在美国硬币体系中，面额为 [1, 5, 10, 25]）。为了避免重新计算值，我们可以使用cache（这种技术称为记忆化）。该makeChange函数是递归函数，负责解决问题，并且由于它是一个内部函数，因此它可以访问cache。

console.log(minCoinChange([1, 5, 10, 25], 37)); // [1, 1, 10, 25]
console.log(minCoinChange([1, 3, 4], 6)) // [3, 3]

贪婪算法

贪婪算法关注的是当时的最佳解，并希望找到全局最优解。与动态规划不同，它没有考虑全局。贪婪算法往往简单直观，但未必是最佳的整体解决方案。

贪婪算法示例：最小硬币找零问题

我们上面动态解决的硬币问题也可以用贪婪算法来解决。该解决方案的最优性取决于传递的面额。

function minCoinChange(coins, amount) {
    const change = [];
    let total = 0;
    for (let i = coins.length; i>= 0; i--) {
        const coin = coins[i];
        while (total + coin <= amount) {
            change.push(coin);
            total += coin;
        }
    }
    return change;
}

如你所见，这个解决方案比动态规划解决方案简单得多。让我们看一些示例参数，看看优化方面的差异：

console.log(minCoinChange([1, 5, 10, 25], 37)); // [25, 10, 1, 1]
console.log(minCoinChange([1, 3, 4], 6)) // [4, 1, 1]

贪婪解决方案为第一个例子给出了最佳结果，但没有为第二个例子给出最佳结果（应该是 [3, 3]，就像我们从动态算法中得到的那样）。

贪婪算法比动态规划算法更简单、更快速，但可能无法始终给出最优解决方案。

回溯算法

回溯算法适合逐步寻找和建立解决方案。

尝试用一种方法解决问题。
如果不起作用，请回溯并选择重复步骤 1，直到找到合适的解决方案。

举个使用回溯的例子，我会另写一篇文章来介绍一个更复杂的算法。我还没想好，但我可能会尝试写一个数独解题器，如果你感兴趣的话，请继续关注！

结论

编程的可能性是无穷无尽的，算法设计也是如此，但我希望本文能帮助您了解一些常见的方法。

文章来源：https://dev.to/christinamcmahon/how-to-design-an-algorithm-2g9c