带你读《图解算法小抄》二十二、贪心算法（2）

带你读《图解算法小抄》二十二、贪心算法（1）https://developer.aliyun.com/article/1347853?groupCode=tech_library

动态规划伪代码框架

function dynamicProgramming(problem) {
  initialize memoization table;
  function dpSolver(subproblem) {
    if (subproblem is already solved) {
      return memoized solution;
    }
    solve subproblem and store the solution in memoization table;
    return solution;
  }
  return dpSolver(original problem);
}

以上是贪心算法和动态规划的基本框架，实际问题的解决需要根据具体情况进行适当的调整和扩展。

5）总结

贪心算法和动态规划是两种常用的算法设计策略。贪心算法通过每次选择局部最优解来构建全局最优解，而动态规划则将问题分解为子问题并通过记忆化存储中间结果来求解最优解。选择使用贪心算法还是动态规划取决于问题的特性，包括问题的最优子结构、重叠子问题性质以及计算开销等因素。

2.分发饼干

1）题目描述

给定两个数组 g 和 s，分别代表孩子的胃口和饼干的尺寸。每个孩子只能得到一块饼干，且只有饼干尺寸大于等于孩子胃口时，孩子才能满足。求解最多能满足几个孩子的需求。

2）解题步骤

为了解决分发饼干的问题，我们可以使用贪心算法来解决。

• 首先对孩子的胃口数组 g 和饼干的尺寸数组 s 进行排序，从小到大。
  
• 使用两个指针 i 和 j 分别指向孩子数组和饼干数组的起始位置。
  
• 遍历孩子数组和饼干数组，比较当前孩子的胃口和当前饼干的尺寸：
  
• 如果当前饼干的尺寸能够满足当前孩子的胃口，将满足的孩子数量加一，并将两个指针都向后移动一位。
  
• 如果当前饼干的尺寸不能满足当前孩子的胃口，将饼干指针向后移动一位，尝试下一块饼干。
  
• 遍历结束后，返回满足的孩子数量作为最终结果。
  

下面是使用贪心算法解决分发饼干问题的算法框架：

function findContentChildren(g, s) {
  g.sort((a, b) => a - b);
  s.sort((a, b) => a - b);  let i = 0;
  let j = 0;
  let count = 0;  while (i < g.length && j < s.length) {
    if (s[j] >= g[i]) {
      count++;
      i++;
      j++;
    } else {
      j++;
    }
  }
  return count;
}

带你读《图解算法小抄》二十二、贪心算法（3）https://developer.aliyun.com/article/1347851?groupCode=tech_library