共计 3065 个字符，预计需要花费 8 分钟才能阅读完成。
第一题 零钱兑换
题目
贪婪（有效）
在日常的生存中，如果咱们要进行零钱兑换，最奢侈的思维天然是
如果能够应用更大面值的硬币，就优先选择它
这也正是贪婪算法的思维
代码
func coinChange(coins []int, amount int) int {
var res int
sort.Ints(coins)
if amount==0{return 0}
for amount>=coins[0]{index:=sort.SearchInts(coins,amount)
if index==len(coins){amount-=coins[len(coins)-1]
res++
continue
}
if coins[index]!=amount {amount-=coins[index-1]
}else{amount-=coins[index]
}
res++
}
if amount!=0 {return -1}
return res
}该解法能够通过测试案例
但无奈提交通过
起因是因为
题目提供的硬币组合不肯定是日常中应用的硬币组合
大面值的硬币不肯定是部分最优解
局部能够应用小面值组合组成的数字无奈应用大面值示意
如果想要持续应用贪婪算法，则须要退出回溯语句，排除应用大面值解的计划，再持续搜寻
因为效率过低，在此不持续进行优化
后续优化思路可参考精选题解
https://leetcode-cn.com/probl…
动静布局
咱们能够发现
寻找硬币组合的过程
实质上能够拆解成为一个一个筛选硬币的后果
例如：
示例 1：
输出：coins = [1, 2, 5], amount = 11
输入：3
解释：11 = 5 + 5 + 1
动静布局的解题过程为本质为求解 dp[11]的过程
在筛选第一个硬币时，有三种筛选的计划
筛选硬币 1，硬币个数为 dp[10]+1
筛选硬币 2，硬币个数为 dp[9]+1
筛选硬币 5，硬币个数为 dp[6]+1
在三个计划中选出个数最小的计划，即为 dp[11]的解
因而能够失去
dp[amount]=min{dp[amount-coins[0],dp[amount-coins[1],…,dp[amount-coins[n-1]}+1
具体代码为
func coinChange(coins []int, amount int) int {
// 初始化数组，因为硬币为整型，筛选的硬币组合个数最大不可能大于面值 amount
max := amount + 1
dp :=make([]int,max)
for i:=range dp{dp[i]=max
}
dp[0] = 0
for i := 1; i <max; i++ {for j := 0; j < len(coins); j++ {if coins[j] <= i {dp[i] = min(dp[i], dp[i - coins[j]] + 1)
}
}
}
if dp[amount]>amount {return -1}else{return dp[amount]
}
}
func min(x int,y int)int{
if x<y{return x}else {return y}
}复杂度剖析
工夫复杂度：O(Sn)，其中 S 是金额 amount，n 是面额数 len(coins)。咱们一共须要计算 O(S) 个状态，S 为题目所给的总金额。对于每个状态，每次须要枚举 n 个面额来转移状态，所以一共须要 O(Sn) 的工夫复杂度。
空间复杂度：O(S)。数组 dp 须要长度为总金额 S 的空间。
第二题 最长回升子序列
题目
思路
子序列的搜寻过程显然具备最有子结构性质
对于 i 长度的序列
能够计算出以第一个元素为开始的前 i - 1 个子序列的最优解
dp[i]的解即为所有满足递增的部分最优解中最长的一个加一
代码
func lengthOfLIS(nums []int) int {if len(nums) == 0 {return 0}
dp := make([]int, len(nums))
dp[0] = 1
maxans := 1
for i := 1; i < len(nums); i++ {dp[i] = 1
for j := 0; j < i; j++ {if nums[i] > nums[j] {dp[i] = max(dp[i], dp[j]+1)
}
}
maxans = max(maxans, dp[i])
}
return maxans
}
func max(x int,y int)int{
if x>y{return x}else{return y}
}复杂度剖析
工夫复杂度：O(n^2)，其中 n 为数组 nums 的长度。动静布局的状态数为 n，计算状态 dp[i] 时，须要 O(n) 的工夫遍历 dp[0…i−1] 的所有状态，所以总工夫复杂度为 O(n^2)
空间复杂度：O(n)，须要额定应用长度为 n 的 dp 数组。
优化 - 贪婪 + 二分
参考官解
https://leetcode-cn.com/probl…
思路与算法
思考一个简略的贪婪，如果咱们要使回升子序列尽可能的长，则咱们须要让序列回升得尽可能慢，因而咱们心愿每次在回升子序列最初加上的那个数尽可能的小。
基于下面的贪婪思路，咱们保护一个数组 d[i]，示意长度为 i 的最长回升子序列的开端元素的最小值，用 l 记录目前最长回升子序列的长度，起始时 l 为 1，d[1]=nums[0]。
同时咱们能够留神到 d[i] 是对于 i 枯燥递增的。因为如果 d[j]≥d[i] 且 j<i，咱们思考从长度为 i 的最长回升子序列的开端删除 i−j 个元素，那么这个序列长度变为 j，且第 j 个元素 x（开端元素）必然小于 d[i]，也就小于 d[j]。那么咱们就找到了一个长度为 j 的最长回升子序列，并且开端元素比 d[j] 小，从而产生了矛盾。因而数组 d 的枯燥性得证。
咱们顺次遍历数组 nums 中的每个元素，并更新数组 d 和 l 的值。如果 nums[i]>d[len] 则更新 len=len+1，否则在 d[1…len]中找满足 d[i−1]<nums[j]<d[i] 的下标 i，并更新 d[i]=nums[j]。
依据 d 数组的枯燥性，咱们能够应用二分查找寻找下标 i，优化工夫复杂度。
最初整个算法流程为：
设以后已求出的最长回升子序列的长度为 len（初始时为 1），从前往后遍历数组 nums，在遍历到 nums[i] 时：
如果 nums[i]>d[len]，则间接退出到 d 数组开端，并更新 len=len+1；
否则，在 d 数组中二分查找，找到第一个比 nums[i] 小的数 d[k]，并更新 d[k+1]=nums[i]。
以输出序列 [0, 8, 4, 12, 2] 为例：
第一步插入 0，d = [0]；
第二步插入 8，d = [0, 8]
第三步插入 4，d = [0, 4]
第四步插入 12，d = [0, 4, 12]
第五步插入 2，d = [0, 2, 12]
最终失去最大递增子序列长度为 3。
代码
func lengthOfLIS(nums []int) int {
l := 1
n := len(nums)
if n == 0 {return 0}
d:=make([]int,n+1)
d[l] = nums[0]
for i := 1; i < n; i++ {if nums[i] > d[l] {
l++
d[l] = nums[i]
} else {
ll := 1
rr := l
pos := 0 // 如果找不到阐明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
for ll <= rr {mid := (ll + rr) >> 1
if d[mid] < nums[i] {
pos = mid
ll = mid + 1
} else {rr = mid - 1}
}
d[pos + 1] = nums[i]
}
}
return l
}复杂度剖析
工夫复杂度：O(nlogn)。数组 nums 的长度为 n，咱们顺次用数组中的元素去更新 d 数组，而更新 d 数组时须要进行 O(logn) 的二分搜寻，所以总工夫复杂度为 O(nlogn)。
空间复杂度：O(n)，须要额定应用长度为 n 的 d 数组。
