贪心算法

贪心算法是一种寻觅最优解的算法思想，它经过部分最优挑选来达到大局最优解。在贪心算法中，每一步都会做出当时状况下的最优挑选，而且假设做出这样的挑选后，剩余的问题可以被简化为一个更小的子问题。

与动态规划不同，贪心算法不需求保存子问题的解，因而一般需求更少的空间和时刻。

贪心算法一般采用一种贪心的战略，即在每一步挑选当时看起来最优的挑选，希望终究得到大局最优解。但是，在某些情况下，部分最优解并不能确保一定可以导致大局最优解。因为贪心算法一旦做出挑选就不能更改。贪心算法仅仅一种近似算法。

贪心算法一般需求满意贪心挑选性质和最优子结构性质，不然它可能会导致过错的结果。

在运用贪心算法时，咱们需求仔细考虑问题的特色和贪心挑选的合理性，并尽可能地证明贪心算法的正确性。假如无法证明贪心算法的正确性，咱们需求考虑运用其他算法来解决问题。

贪心算法常见的使用场景包括：

• 贪心挑选性质：在求解最优解的进程中，每一步的挑选只与当时状况有关，不受之前挑选的影响。
• 最优子结构性质：问题的最优解可以被分解为若干个子问题的最优解，即子问题的最优解可以推导出原问题的最优解。
• 无后效性：某个状况曾经的进程不会影响以后的状况，只与当时状况有关。

举个反例：279. 彻底平方数

给你一个整数n，返回和为n的彻底平方数的最少数量。

彻底平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9和16都是彻底平方数，而3和11不是。

示例1：

输入： n = 12
输出： 3 
解说： 12 = 4 + 4 + 4

示例 2：

输入： n = 13
输出： 2
解说： 13 = 4 + 9

提示：

• 1<=n<=1041 <= n <= 10^41<=n<=104

过错做法：

class Solution:
    def numSquares(self, n: int) -> int:
        count = 0
        while n != 0:
            c = int(n**(1/2))
            n -= c**2
            count += 1
        return count

输入12的时候答案是4，也便是12 = 9 + 1 + 1 + 1，

实际上应该是答案为3，12 = 4 + 4 + 4。

这个函数运用的是贪心算法的思想，每次都挑选当时能用的最大彻底平方数来减去 n，直到 n 减为 0。

在每一步中，挑选最大的彻底平方数来减去 n，可以确保所需的彻底平方数的数量最小，因为假如咱们挑选了小的彻底平方数，那么咱们需求更多的彻底平方数才干表明 n。

但是它并没有证明贪心战略的正确性，也没有提供正确性的证明。咱们现已提供反例，证明这玩意儿是错的了。贪心算法的正确性得不到确保，所以本题不能用贪心算法。

正确答案：

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [float('inf')]*(n+1)
        dp[0] = 0
        for i in range(1,n+1):
            j = 1
            while j*j <= i:
                dp[i] = min(dp[i],dp[i-j*j]+1)
                j+=1
        return dp[-1]

这个代码运用了动态规划来解决彻底平方数问题，它的时刻复杂度为 O(nn)O(n\sqrt{n})O(nn​)，空间复杂度为 $O(n)$。

• 当 i=0 时，不需求任何彻底平方数。

• 对于 i>0 的情况，咱们枚举从 1 到 i 中的每个彻底平方数 j*j，然后核算 dp[i-j*j]+1 的值，这个值表明在将 i-j*j 分解成彻底平方数之和的基础上再加上一个彻底平方数 j*j。咱们需求使 dp[i-j*j]+1 的值最小，因而咱们可以得出状况搬运方程：

最终，dp[n] 的值便是将 n 分解成彻底平方数之和所需的最小个数。

该代码正确地解决了彻底平方数问题，可以得到大局最优解。

55. 跳动游戏

给定一个非负整数数组nums，你最初坐落数组的第一个下标。

数组中的每个元素代表你在该方位可以跳动的最大长度。

判别你是否可以抵达最终一个下标。

示例1：

输入： nums = [2,3,1,1,4]
输出： true
解说： 可以先跳 1 步，从下标 0 抵达下标 1, 然后再从下标 1 跳 3 步抵达最终一个下标。

示例2：

输入： nums = [3,2,1,0,4]
输出： false
解说： 无论怎样，总会抵达下标为 3 的方位。但该下标的最大跳动长度是 0 ， 所以永久不可能抵达最终一个下标。

提示：

• 1 <= nums.length <= 3 * 104
• 0 <= nums[i] <= 105

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        maxlen = 0
        for i,n in enumerate(nums):
            if maxlen < i:
                return False
            maxlen = max(maxlen,i+n)
        return maxlen >= len(nums) -1 

这段代码实现了一个十分经典的贪心算法，用于判别能否从数组的起点跳到终点。

具体思路是，用 maxlen 记录当时能抵达的最远方位，遍历数组中的每个方位，假如当时方位大于 maxlen，阐明无法抵达该方位，直接返回 False。不然，更新 maxlen 为当时方位可以抵达的最远方位。

这个算法的贪心战略是，在每个方位上都挑选可以抵达的最远方位。因为跳动的步数只能是整数，所以假如当时方位能抵达的最远方位小于当时方位，那么就无法抵达该方位。

这个算法的时刻复杂度是 $O(n)$，空间复杂度是 $O(1)$。

45. 跳动游戏 II

给定一个长度为n的0 索引整数数组nums。初始方位为nums[0]。

每个元素nums[i]表明从索引i向前跳转的最大长度。换句话说，假如你在nums[i]处，你可以跳转到恣意nums[i + j]处:

• 0 <= j <= nums[i]
• i + j < n

返回抵达nums[n - 1]的最小跳动次数。生成的测试用例可以抵达nums[n - 1]。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解说: 跳到最终一个方位的最小跳动数是 2。
    从下标为 0 跳到下标为 1 的方位，跳1步，然后跳3步抵达数组的最终一个方位。

示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

提示:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 1000
• 标题确保可以抵达nums[n-1]

class Solution:
    def jump(self, nums) -> int:
        minstep = 0
        i = len(nums) - 1
        while i > 0:
            for j,n in enumerate(nums):
                if j+n >= i:
                    minstep += 1
                    i = j
                    break
        return minstep

该算法的时刻复杂度为 O(n2)O(n^2)O(n2)，其间 $n$ 为数组的长度。

在最坏情况下，每个元素都需求遍历一遍，以找到它们可以抵达的最远间隔，这需求 $O(n)$ 的时刻复杂度。同时，每次找到可以抵达 $i$ 的最远间隔时，都需求遍历从 $0$ 到 $i-1$ 的一切元素，以找到可以抵达 $i$ 的最小步数，这也需求 $O(n)$ 的时刻复杂度。因而，总时刻复杂度为 O(n2)O(n^2)O(n2)。

该算法的空间复杂度为 $O(1)$，因为它只运用了常数级别的额外空间。

优化——早年往后跳：

这个算法是一个根据贪心战略的解法，跟之前的早年往后跳的贪心算法类似，不过稍微做了一些改进，可以将时刻复杂度降低到 $O(n)$。

算法的中心思想是保护一个区间 [0, end]，在这个区间内每个方位所能跳到的最远间隔都是 i + nums[i]，其间 i 是当时方位，nums[i] 是当时方位所能跳的最远间隔。保护的时候，咱们不断更新可以抵达的最远间隔 maxlen，当 i 抵达区间的结尾 end 时，阐明需求跳一步，并将 end 更新为 maxlen。

这个算法的时刻复杂度为 $O(n)$，空间复杂度为 $O(1)$。

class Solution:
    def jump(self, nums):
        n = len(nums)
        maxlen = end = 0
        step = 0
        for i in range(n - 1):
            maxlen = max(maxlen, i + nums[i])
            if i == end:
                end = maxlen
                step += 1
        return step