🎯 动态规划与贪心算法

从零开始理解两大经典算法思想

1动态规划 (Dynamic Programming)

📖 什么是动态规划？

动态规划（Dynamic Programming，简称DP）是一种通过将复杂问题分解成子问题，并保存子问题的解（避免重复计算）来解决问题的算法思想。

核心思想：把原问题分解为相对简单的子问题，通过求解子问题得到原问题的解。关键在于记录子问题的解，避免重复计算。

🎯 解决什么问题？

动态规划主要用于解决具有重叠子问题和最优子结构的问题：

特征 说明 示例
重叠子问题 子问题被重复计算多次 斐波那契数列：F(n) = F(n-1) + F(n-2)
最优子结构 问题的最优解包含子问题的最优解 最短路径：A→C的最短路径包含A→B的最短路径
无后效性 当前状态确定后，之后的决策只受当前状态影响 背包问题：选择第i个物品后，只影响剩余容量

🛠️ 解题步骤

  1. 定义状态：确定DP数组的含义，dp[i]或dp[i][j]表示什么
  2. 状态转移方程：找出当前状态与之前状态的关系
  3. 初始化：确定边界条件，dp[0]、dp[0][0]等
  4. 计算顺序：确定是从小到大还是从大到小计算
  5. 返回结果：根据DP数组得到最终答案

📝 经典算法题

题目1：斐波那契数列 简单

问题描述：求第n个斐波那契数，F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)

解题思路：
  1. 定义状态：dp[i]表示第i个斐波那契数
  2. 状态转移：dp[i] = dp[i-1] + dp[i-2]
  3. 初始化：dp[0]=0, dp[1]=1
// 方法1：动态规划（空间优化版）
function fib(n) {
  if (n < 2) return n;
  let prev = 0, curr = 1;
  for (let i = 2; i <= n; i++) {
    [prev, curr] = [curr, prev + curr];
  }
  return curr;
}

// 时间复杂度：O(n)，空间复杂度：O(1)
题目2：爬楼梯 简单

问题描述：假设你正在爬楼梯，需要n阶才能到达楼顶。每次可以爬1或2个台阶，有多少种不同的方法可以爬到楼顶？

解题思路：
  1. 到第i阶的方法数 = 到第i-1阶的方法数 + 到第i-2阶的方法数
  2. 因为只能从i-1（爬1阶）或i-2（爬2阶）到达i
  3. 这就是斐波那契数列的变种
// 动态规划解法
function climbStairs(n) {
  if (n <= 2) return n;
  let dp = new Array(n + 1);
  dp[1] = 1;
  dp[2] = 2;
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}
题目3：0-1背包问题 中等

问题描述：有n件物品和一个容量为W的背包。第i件物品的重量是w[i]，价值是v[i]。每件物品只能选一次，求最大总价值。

解题思路：
  1. 定义状态：dp[i][j]表示前i个物品，容量为j时的最大价值
  2. 状态转移：
    • 不选第i个物品：dp[i][j] = dp[i-1][j]
    • 选第i个物品（需要j >= w[i]）：dp[i][j] = dp[i-1][j-w[i]] + v[i]
    • 取两者最大值
  3. 空间优化：可以用一维数组从后往前遍历
// 0-1背包问题 - 空间优化版
function knapsack(W, weights, values) {
  let n = weights.length;
  let dp = new Array(W + 1).fill(0);

  for (let i = 0; i < n; i++) {
    for (let j = W; j >= weights[i]; j--) {
      dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
    }
  }

  return dp[W];
}

// 时间复杂度：O(nW)，空间复杂度：O(W)
💡 注意：0-1背包的倒序遍历很重要！如果是完全背包（物品可重复选择），则需要正序遍历。
题目4：最长公共子序列 (LCS) 中等

问题描述：给定两个字符串text1和text2，返回这两个字符串的最长公共子序列的长度。

解题思路：
  1. 定义状态：dp[i][j]表示text1[0:i]和text2[0:j]的LCS长度
  2. 状态转移：
    • 如果text1[i-1] == text2[j-1]：dp[i][j] = dp[i-1][j-1] + 1
    • 否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])
// 最长公共子序列
function longestCommonSubsequence(text1, text2) {
  let m = text1.length, n = text2.length;
  let dp = new Array(m + 1).fill(0).map(function() {
    return new Array(n + 1).fill(0);
  });

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[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]);
      }
    }
  }

  return dp[m][n];
}
题目5：最长递增子序列 (LIS) 中等

问题描述：给定一个未排序的整数数组，找到最长递增子序列的长度。

解题思路：
  1. 方法1（O(n²)）：dp[i]表示以nums[i]结尾的最长递增子序列长度
  2. 对于每个i，遍历j < i，如果nums[j] < nums[i]，则dp[i] = max(dp[i], dp[j]+1)
  3. 方法2（O(nlogn)）：维护一个递增数组，用二分查找优化
// 方法1：动态规划 O(n²)
function lengthOfLIS(nums) {
  let n = nums.length;
  let dp = new Array(n).fill(1);
  let maxLen = 1;

  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
    maxLen = Math.max(maxLen, dp[i]);
  }

  return maxLen;
}
题目6：编辑距离 困难

问题描述：给定两个单词word1和word2，计算出将word1转换成word2所使用的最少操作数。你可以对一个单词进行三种操作：插入、删除、替换。

解题思路：
  1. 定义状态：dp[i][j]表示word1[0:i]转换成word2[0:j]的最少操作数
  2. 状态转移：
    • 如果word1[i-1] == word2[j-1]：dp[i][j] = dp[i-1][j-1]
    • 否则：dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
// 编辑距离
function minDistance(word1, word2) {
  let m = word1.length, n = word2.length;
  let dp = new Array(m + 1).fill(0).map(function() {
    return new Array(n + 1).fill(0);
  });

  // 初始化
  for (let i = 0; i <= m; i++) dp[i][0] = i;
  for (let j = 0; j <= n; j++) dp[0][j] = j;

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j], // 删除
          dp[i][j - 1], // 插入
          dp[i - 1][j - 1] // 替换
        );
      }
    }
  }

  return dp[m][n];
}

2贪心算法 (Greedy Algorithm)

📖 什么是贪心算法？

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下的最优选择（局部最优），从而希望导致全局最优的算法。

核心思想：每一步都做出当前看起来最好的选择，不考虑整体最优性。就像人常说的"贪心"一样，只顾眼前利益。

🎯 解决什么问题？

贪心算法适用于具有贪心选择性质和最优子结构的问题：

特征 说明 示例
贪心选择性质 全局最优解可以通过局部最优选择达到 活动选择：每次选结束最早的活动
最优子结构 问题的最优解包含子问题的最优解 最小生成树：去掉一条边后子问题仍最优
无后效性 当前选择不影响之后的选择 哈夫曼编码：每次合并最小的两个节点
⚠️ 注意：贪心算法不一定能得到全局最优解！只有当问题具有"贪心选择性质"时，贪心算法才有效。

🛠️ 解题步骤

  1. 问题分解：将问题分解成多个步骤
  2. 贪心策略：确定每一步的贪心选择标准（什么是最好的选择）
  3. 证明正确性：证明贪心选择性质成立（这一步很重要！）
  4. 实现算法：按照贪心策略编写代码

📝 经典算法题

题目1：活动选择问题 简单

问题描述：给定n个活动的开始时间和结束时间，选择最多的互不重叠的活动。

贪心策略：
  1. 按照活动的结束时间排序
  2. 每次选择结束时间最早且与已选活动不冲突的活动
  3. 为什么有效？选择结束最早的活动，给后面留下更多时间
// 活动选择问题
function activitySelection(activities) {
  // activities: [{start: 1, end: 4}, {start: 3, end: 5}, ...]
  activities.sort(function(a, b) { return a.end - b.end; });

  let selected = [];
  let lastEnd = 0;

  for (let act of activities) {
    if (act.start >= lastEnd) {
      selected.push(act);
      lastEnd = act.end;
    }
  }

  return selected;
}
题目2：分发饼干 简单

问题描述：每个孩子有一个胃口值g[i]，每个饼干有一个尺寸s[j]。如果饼干尺寸>=孩子胃口，就可以满足该孩子。求最多能满足多少孩子？

贪心策略：
  1. 将孩子胃口和饼干尺寸都从小到大排序
  2. 用最小的能满足当前孩子的饼干去满足他
  3. 为什么有效？优先满足小胃口的孩子，节省大饼干给大胃口的孩子
// 分发饼干
function findContentChildren(g, s) {
  g.sort(function(a, b) { return a - b; });
  s.sort(function(a, b) { return a - b; });

  let i = 0, j = 0;
  while (i < g.length && j < s.length) {
    if (s[j] >= g[i]) {
      i++; // 满足了一个孩子
    }
    j++; // 饼干被使用（无论是否满足）
  }

  return i;
}
题目3：跳跃游戏 中等

问题描述：给定一个非负整数数组nums，最初位于数组的第一个下标。每个元素表示你在该位置可以跳跃的最大长度。判断是否能够到达最后一个下标。

贪心策略：
  1. 维护一个变量reach表示当前能到达的最远位置
  2. 遍历数组，如果当前位置<=reach，则更新reach = max(reach, i+nums[i])
  3. 如果reach >= n-1，则可以到达终点
// 跳跃游戏
function canJump(nums) {
  let n = nums.length;
  let reach = 0;

  for (let i = 0; i < n; i++) {
    if (i > reach) return false; // 当前位置不可达
    reach = Math.max(reach, i + nums[i]);
    if (reach >= n - 1) return true;
  }

  return true;
}
题目4：划分字母区间 中等

问题描述：字符串S由小写字母组成。要把字符串分割成尽可能多的片段，同一个字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

贪心策略：
  1. 先记录每个字母最后出现的位置
  2. 遍历字符串，当前片段的结束位置 = max(片段中所有字母的最后出现位置)
  3. 当遍历到结束位置时，完成一个片段
// 划分字母区间
function partitionLabels(S) {
  let last = {};
  for (let i = 0; i < S.length; i++) {
    last[S[i]] = i;
  }

  let result = [];
  let start = 0, end = 0;

  for (let i = 0; i < S.length; i++) {
    end = Math.max(end, last[S[i]]);
    if (i === end) {
      result.push(end - start + 1);
      start = i + 1;
    }
  }

  return result;
}
题目5：哈夫曼编码 困难

问题描述：给定一组字符及其出现频率，构造哈夫曼树，使得编码后的总长度最短。

贪心策略：
  1. 每次从所有节点中选择频率最小的两个节点
  2. 创建一个新的父节点，频率为两者之和
  3. 重复直到只剩一个节点（根节点）
  4. 为什么有效？频率高的字符编码短，频率低的字符编码长，总长度最短
// 哈夫曼编码（使用优先队列/最小堆）
class Node {
  constructor(char, freq) {
    this.char = char;
    this.freq = freq;
    this.left = null;
    this.right = null;
  }
}

function huffmanCoding(chars, freqs) {
  let heap = [];
  for (let i = 0; i < chars.length; i++) {
    heap.push(new Node(chars[i], freqs[i]));
  }

  heap.sort(function(a, b) { return a.freq - b.freq; });

  while (heap.length > 1) {
    let left = heap.shift();
    let right = heap.shift();
    let parent = new Node(null, left.freq + right.freq);
    parent.left = left;
    parent.right = right;
    heap.push(parent);
    heap.sort(function(a, b) { return a.freq - b.freq; });
  }

  return heap[0]; // 返回哈夫曼树的根节点
}
题目6：最小生成树 (Prim算法) 困难

问题描述：给定一个带权无向图，找出一棵生成树，使得所有边的权值之和最小。

贪心策略（Prim算法）：
  1. 从任意一个顶点开始，将其加入最小生成树集合
  2. 每次选择连接集合内和集合外顶点的最小权值边
  3. 将该边和另一个顶点加入集合
  4. 重复直到所有顶点都在集合中
// Prim算法求最小生成树
function prim(graph) {
  let n = graph.length;
  let visited = new Array(n).fill(false);
  let minCost = new Array(n).fill(Infinity);
  minCost[0] = 0;

  let totalCost = 0;

  for (let i = 0; i < n; i++) {
    let u = -1;
    for (let j = 0; j < n; j++) {
      if (!visited[j] && (u === -1 || minCost[j] < minCost[u])) {
        u = j;
      }
    }

    visited[u] = true;
    totalCost += minCost[u];

    for (let v = 0; v < n; v++) {
      if (!visited[v] && graph[u][v] < minCost[v]) {
        minCost[v] = graph[u][v];
      }
    }
  }

  return totalCost;
}

3动态规划 vs 贪心算法

对比维度 动态规划 贪心算法
核心思想 记录所有子问题的解，通过组合得到原问题的解 每一步都做出当前最好的选择
适用范围 具有重叠子问题和最优子结构的问题 具有贪心选择性质的问题
全局最优性 一定能得到全局最优解 不一定能得到全局最优解
时间复杂度 通常较高（需要计算所有子问题） 通常较低（只需要一次遍历）
空间复杂度 通常需要额外的DP数组 通常只需要常数空间
证明难度 相对容易（只要定义好状态和转移） 较难（需要证明贪心选择性质）
示例问题 背包问题、LCS、编辑距离 活动选择、哈夫曼编码、最小生成树
💡 如何选择？
  • 如果问题具有贪心选择性质，优先用贪心（效率高）
  • 如果贪心不保证最优，或者你不确定，用动态规划（保证最优）
  • 如果问题有明显的重叠子问题，用动态规划
  • 如果问题要求所有解或最优解，用动态规划

🔍 经典对比案例

案例：背包问题

0-1背包问题（每个物品只能选一次）：

  • ❌ 贪心算法失效！（按价值密度排序选择不一定最优）
  • ✅ 必须用动态规划

分数背包问题（物品可以选一部分）：

  • ✅ 贪心算法有效！（按价值密度排序，依次选取）
  • ✅ 动态规划也可以，但贪心更高效
💡 启示：同样的问题，稍微改变条件（0-1 vs 分数），就会影响贪心算法是否适用。所以使用贪心前一定要证明正确性！

4学习建议与练习路径

📚 动态规划学习路径

  1. 入门：斐波那契数列、爬楼梯、打家劫舍
  2. 进阶：背包问题、最长公共子序列、最长递增子序列
  3. 高级：编辑距离、正则表达式匹配、股票买卖系列
  4. 大师：区间DP、树形DP、状态压缩DP

📚 贪心算法学习路径

  1. 入门：活动选择、分发饼干、跳跃游戏I
  2. 进阶：划分字母区间、无重叠区间、用最少数量的箭引爆气球
  3. 高级：哈夫曼编码、最小生成树、最短路径（Dijkstra）

🎯 刷题建议

  • LeetCode：搜索"Dynamic Programming"和"Greedy"标签
  • 先看懂：每个经典问题都要能独立写出状态转移方程
  • 再刷题：同类问题刷3-5道，形成肌肉记忆
  • 总结模板：比如背包问题、LCS、编辑距离都有固定模板
  • 手写代码：不要只看答案，要能白板编程

📌 常见错误

动态规划常见错误：
  • ❌ 状态定义不清晰
  • ❌ 状态转移方程写错
  • ❌ 初始化条件错误
  • ❌ 计算顺序搞反（比如完全背包正序遍历写成倒序）
贪心算法常见错误：
  • ❌ 没有证明贪心选择性质就用贪心
  • ❌ 贪心策略和排序策略不匹配
  • ❌ 忽略边界条件