贪心算法

所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅仅是在某种意义上的局部最优解。贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性（即某个状态以后的过程不会影响以前的状态，只与当前状态有关）。所以，对所采用的贪心策略一定要仔细分析其是否满足无后效性。

✏️ 贪心选择性质

贪心选择性质（greedy-choice property）：所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，换句话说，当考虑做何种选择的时候，我们只考虑对当前问题最佳的选择而不考虑子问题的结果。这是贪心算法可行的第一个基本要素。贪心算法以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。

✏️ 题型

1、jump-game-ii

给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。假设你总是可以到达数组的最后一个位置。

// 1、每次用 当前位置的最小步数加1 来更新 当前位置可以到达的所有位置的步数 （超时）
int jump(vector<int>& nums) {
    int len = nums.size();
    std::vector<int> dp(len, len);
    dp[0] = 0;
    for(int i = 0;i < len;i++){
        for(int j = 1;j <= nums[i] && i + j < len;j++){
            dp[i + j] = std::min(dp[i + j], dp[i] + 1);
        }
    }
    return dp[len - 1];
}

✏️ 贪心与动态规划

动态规划具有两个性质：

1. 重叠子问题

2. 最优子结构

贪心算法：

1. 贪心选择性质

2. 最优子结构

解释一下，最优子结构性质是指问题的最优解包含其子问题的最优解时，就称该问题具有最优子结构性质，重叠子问题指的是子问题可能被多次用到，多次计算，动态规划就是为了消除其重叠子问题而设计的。其实贪心算法是一种特殊的动态规划，由于其具有贪心选择性质，保证了子问题只会被计算一次，不会被多次计算，因此贪心算法其实是最简单的动态规划。