贪心算法

贪心算法是一种寻找最优解的算法思想，它通过局部最优选择来达到全局最优解。在贪心算法中，每一步都会做出当前状态下的最优选择，并且假设做出这样的选择后，剩余的问题可以被简化为一个更小的子问题。

与动态规划不同，贪心算法不需要保存子问题的解，因此通常需要更少的空间和时间。

贪心算法通常采用一种贪心的策略，即在每一步选择当前看起来最优的选择，希望最终得到全局最优解。但是，在某些情况下，局部最优解并不能保证一定能够导致全局最优解。由于贪心算法一旦做出选择就不能更改。贪心算法只是一种近似算法。

贪心算法通常需要满足贪心选择性质和最优子结构性质，否则它可能会导致错误的结果。

在使用贪心算法时，我们需要仔细考虑问题的特点和贪心选择的合理性，并尽可能地证明贪心算法的正确性。如果无法证明贪心算法的正确性，我们需要考虑使用其他算法来解决问题。

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

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

举个反例🌰：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