题目描述
给你一个整数 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 <= 10^4
动态规划生成杨辉三角：层序构建与递推关系（LeetCode 118）
组合总和问题：回溯与剪枝策略应用（面试题）
贪心算法求解最小跳跃次数（LeetCode 45）
题目描述
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处（0 <= j <= nums[i] 且 i + j < n）
返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 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 <= 10^40 <= nums[i] <= 1000- 题目保证可以到达
n - 1
贪心算法判断数组终点可达性：维护最大位置（LeetCode 55）
题目描述
给你一个非负整数数组 nums ，你最初位于数组的第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
示例 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 <= 10^40 <= nums[i] <= 10^5
一次遍历计算买卖股票的最佳时机（LeetCode 121）
题目描述
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1:
输入：
prices = [7, 1, 5, 3, 6, 4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2:
输入：
prices = [7, 6, 4, 3, 1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
提示:
1 <= prices.length <= 10^50 <= prices[i] <= 10^4