20 | 算法思想：JS中分治、贪心、回溯和动态规划-JavaScript进阶实战

当前位置:　首页>> 技术小册>> JavaScript进阶实战

20 | 算法思想：JS中分治、贪心、回溯和动态规划

在JavaScript编程的进阶之旅中，掌握高效的算法思想是提升代码性能、解决复杂问题的关键。本章将深入探讨四种在算法设计中极为重要且广泛应用的策略：分治、贪心、回溯和动态规划。每种策略都有其独特的适用场景和解决问题的方式，理解并熟练运用它们，将极大地拓宽你的编程视野和问题解决能力。

20.1 分治策略（Divide and Conquer）

分治策略是一种将复杂问题分解成若干个简单子问题来解决，然后合并子问题的解以得到原问题的解的算法设计策略。其核心思想在于“分而治之”，即将大问题划分为小问题，解决小问题，然后将解决的小问题合并起来，从而完成对整个大问题的求解。

案例：归并排序

归并排序是分治策略的经典应用之一。它将数组分成两半，对每半部分递归地应用归并排序，然后将排序好的两半合并在一起。以下是JavaScript实现的归并排序示例：

function mergeSort(arr) {
    if (arr.length <= 1) return arr;
    const middle = Math.floor(arr.length / 2);
    const left = arr.slice(0, middle);
    const right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
    let result = [], indexLeft = 0, indexRight = 0;
    while (indexLeft < left.length && indexRight < right.length) {
        if (left[indexLeft] < right[indexRight]) {
            result.push(left[indexLeft]);
            indexLeft++;
        } else {
            result.push(right[indexRight]);
            indexRight++;
        }
    }
    return result.concat(left.slice(indexLeft)).concat(right.slice(indexRight));
}

20.2 贪心策略（Greedy Algorithm）

贪心算法总是做出在当前看来最好的选择，即它希望通过所做的局部最优选择来达到全局最优解。需要注意的是，贪心算法并不总能保证得到全局最优解，但它因其简单高效而得到广泛应用。

案例：活动选择问题

给定一系列活动，每个活动都有一个开始时间和一个结束时间，求可以安排的最大活动数量，使得没有两个活动的时间区间重叠。这个问题可以使用贪心算法解决，策略是选择最早结束的活动，因为它为后面的活动留下了最多的选择空间。

function maxActivities(activities) {
    activities.sort((a, b) => a.finish - b.finish); // 按结束时间排序
    let count = 1;
    let lastEnd = activities[0].finish;
    for (let i = 1; i < activities.length; i++) {
        if (activities[i].start >= lastEnd) {
            count++;
            lastEnd = activities[i].finish;
        }
    }
    return count;
}

20.3 回溯算法（Backtracking）

回溯算法是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化来撤销上一步或上几步的计算，再通过不同的途径来探索其他的候选解。

案例：N皇后问题

N皇后问题是一个经典的回溯算法问题，要求在N×N的棋盘上放置N个皇后，使得她们互不攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

function solveNQueens(n) {
    let result = [];
    let board = Array.from({ length: n }, () => Array(n).fill('.'));
    function isSafe(row, col) {
        // 检查列和两对角线
        for (let i = 0; i < row; i++) {
            if (board[i][col] === 'Q' || board[i][col - row + i] === 'Q' || board[i][col + row - i] === 'Q') {
                return false;
            }
        }
        return true;
    }
    function solve(row) {
        if (row === n) {
            result.push(board.map(row => row.join('')));
            return;
        }
        for (let col = 0; col < n; col++) {
            if (isSafe(row, col)) {
                board[row][col] = 'Q';
                solve(row + 1);
                board[row][col] = '.'; // 回溯
            }
        }
    }
    solve(0);
    return result;
}

20.4 动态规划（Dynamic Programming）

动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。它存储子问题的解以避免重复计算，通常用于解决最优化问题。

案例：斐波那契数列

斐波那契数列是一个经典的动态规划问题，其中每个数字是前两个数字的和。动态规划通过自底向上的方式计算每个斐波那契数，避免了重复计算。

function fibonacci(n) {
    if (n <= 1) return n;
    let dp = Array(n + 1).fill(0);
    dp[1] = 1;
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

案例：最长公共子序列（LCS）

最长公共子序列问题是另一个典型的动态规划应用。给定两个字符串，找到它们之间的最长公共子序列。

function longestCommonSubsequence(s1, s2) {
    const m = s1.length, n = s2.length;
    let dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (s1[i - 1] === s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    // 构建LCS
    let lcs = '';
    let i = m, j = n;
    while (i > 0 && j > 0) {
        if (s1[i - 1] === s2[j - 1]) {
            lcs = s1[i - 1] + lcs;
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }
    return lcs;
}