前端机试：DP 与贪心算法高效准备策略

你作为前端开发者，目前不了解动态规划（DP）和贪心算法，希望知道如何高效准备机试中的这类题目，核心目标是能掌握解题思路并写出可运行的代码。结合前端的学习特点和机试的实际需求，我会从“基础认知→核心解题思路→刷题策略→前端适配”四个维度帮你梳理。

---

一、先建立核心认知：DP和贪心的本质区别

作为前端新手，不用先啃复杂理论，先记住最核心的区别：

• 动态规划（DP）：解决“有重叠子问题+最优子结构”的问题，核心是「记录子问题答案」（记忆化），避免重复计算。比如“爬楼梯”，算第n阶的方法数需要用到n-1和n-2阶的结果，把这些结果存起来就能避免重复算。

• 贪心算法：每一步都选「当前局部最优」的选择，最终希望得到全局最优。但贪心不是万能的，只有问题满足“贪心选择性质”（局部最优能推全局最优）时才适用。比如“找零钱”（标准硬币面额），优先用大面额凑就是贪心。

---

二、动态规划（DP）：从“模板化”入手（前端友好版）

DP的难点是推导“状态转移方程”，但机试中高频的DP题都有固定套路，先掌握「核心三要素」，再刷入门题。

1. DP解题核心三要素（必记）

要素	含义
状态定义	定义dp[i]/dp[i][j]代表什么（比如dp[i]是“到第i阶楼梯的方法数”）
状态转移方程	如何从子问题的答案推导出当前问题的答案（比如dp[i] = dp[i-1] + dp[i-2]）
初始条件	最基础的子问题答案（比如dp[1]=1，1阶楼梯只有1种走法）

2. 入门例题（JS实现，机试高频）

例1：爬楼梯（LeetCode 70，线性DP）

问题：每次只能走1或2步，求到第n阶的方法数。

function climbStairs(n) {
  // 边界处理：前端机试必做，避免n=0/1/2时出错
  if (n <= 2) return n;
  
  // 1. 状态定义：dp[i] = 到第i阶的方法数
  const dp = new Array(n + 1);
  
  // 2. 初始条件
  dp[1] = 1;
  dp[2] = 2;
  
  // 3. 状态转移：遍历计算每个子问题
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  
  return dp[n];
}

// 测试用例
console.log(climbStairs(3)); // 3（1+1+1 / 1+2 / 2+1）
console.log(climbStairs(5)); // 8

前端优化：不用数组，用两个变量节省空间（机试常考优化）：

function climbStairs(n) {
  if (n <= 2) return n;
  let prev1 = 1, prev2 = 2; // 分别存dp[i-2]和dp[i-1]
  for (let i = 3; i <= n; i++) {
    const temp = prev1 + prev2;
    prev1 = prev2;
    prev2 = temp;
  }
  return prev2;
}

例2：最大子数组和（LeetCode 53，线性DP）

问题：找一个数组中连续子数组的最大和（前端机试高频）。

function maxSubArray(nums) {
  // 边界处理：空数组
  if (nums.length === 0) return 0;
  
  // 1. 状态定义：dp[i] = 以nums[i]结尾的最大子数组和
  const dp = new Array(nums.length);
  // 2. 初始条件：第一个元素的最大和就是自己
  dp[0] = nums[0];
  // 3. 状态转移：要么接上前一个子数组，要么重新开始
  let max = dp[0]; // 记录全局最大值
  for (let i = 1; i < nums.length; i++) {
    dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
    max = Math.max(max, dp[i]);
  }
  return max;
}

// 测试用例
console.log(maxSubArray([-2,1,-3,4,-1,2,1,-5,4])); // 6（[4,-1,2,1]）

3. 机试高频DP类型（前端重点刷）

不用贪多，优先掌握这3类，覆盖80%前端机试DP题：

• 线性DP（爬楼梯、最大子数组和、打家劫舍）

• 子序列问题（最长递增子序列LIS）

• 简单背包问题（01背包、完全背包，比如“给定物品和容量，求最大价值”）

---

三、贪心算法：先选“策略”，再验证

贪心的关键是「选对贪心策略」，机试中贪心题大多和“排序”绑定，步骤更简单。

1. 贪心解题核心步骤

1. 确定贪心策略（比如“按面额从大到小找零”“按区间结束时间排序选最多不重叠区间”）；

2. 验证策略是否正确（举反例，比如面额[1,3,4]凑6，贪心选4+1+1不如3+3，说明贪心不适用）；

3. 编码实现（排序+遍历选择）。

2. 入门例题（JS实现）

例1：买卖股票的最佳时机II（LeetCode 122，贪心）

问题：可以多次买卖股票，求最大利润（只要后一天比前一天贵就卖）。

function maxProfit(prices) {
  let profit = 0;
  // 贪心策略：只要当天价格>前一天，就赚差价
  for (let i = 1; i < prices.length; i++) {
    if (prices[i] > prices[i - 1]) {
      profit += prices[i] - prices[i - 1];
    }
  }
  return profit;
}

// 测试用例
console.log(maxProfit([7,1,5,3,6,4])); // 7（5-1 + 6-3）

例2：分发饼干（LeetCode 455，贪心）

问题：用饼干满足孩子的胃口，每个孩子只能吃一个饼干，求最多满足多少孩子。

function findContentChildren(g, s) {
  // 贪心策略：先排序，用最小的饼干满足最小的胃口
  g.sort((a, b) => a - b); // 孩子胃口排序
  s.sort((a, b) => a - b); // 饼干尺寸排序
  
  let child = 0, cookie = 0;
  while (child < g.length && cookie < s.length) {
    if (s[cookie] >= g[child]) {
      child++; // 满足一个孩子
    }
    cookie++; // 饼干要么用了，要么不够用，都要换下一个
  }
  return child;
}

// 测试用例
console.log(findContentChildren([1,2,3], [1,1])); // 1
console.log(findContentChildren([1,2], [1,2,3])); // 2

---

四、前端机试准备的核心策略

1. 刷题优先级（从易到难，建立信心）

阶段	目标	推荐题目（LeetCode）
入门	掌握核心思路	DP：70、53、198；贪心：122、455
进阶	熟悉模板	DP：300（LIS）、416（分割等和子集）；贪心：435（区间调度）
冲刺	适配机试	刷目标公司的前端机试真题（牛客网、力扣企业题库）

2. 前端专属注意点

• 输入输出处理：机试多在Node.js环境，学会用readline读取输入：

  
  const readline = require('readline');
  const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
  });
  rl.question('请输入楼梯阶数：', (n) => {
    console.log(climbStairs(Number(n)));
    rl.close();
  });

• 边界条件：前端容易忽略n=0、空数组、负数等情况，机试中这些是扣分点；

• 空间优化：DP题优先用“滚动变量”（比如爬楼梯的双变量），减少数组使用，代码更简洁。

3. 复盘技巧

• 做错的题按“DP/贪心”分类，标注错因（比如“状态转移方程推错”“贪心策略选反”）；

• 把高频题的解题模板记下来（比如DP三要素、贪心排序策略），机试前快速过一遍。

---

总结

1. DP核心：记住「状态定义、转移方程、初始条件」三要素，优先刷线性DP入门，用JS实现并优化空间；

2. 贪心核心：先确定排序类贪心策略，验证是否有反例，再编码；

3. 机试技巧：前端重点处理边界条件和输入输出，优先刷入门题建立信心，不用死磕难题。

按这个思路准备，2-3周就能应对前端机试中80%的DP和贪心基础题，核心是“模板化解题+刻意练习”，而非死记理论。

（注：文档部分内容可能由 AI 生成）