Leetcode题解（9）- 2018 力扣 Leetcode CN 高频题汇总 part 5 排序检索、动态规划
# 排序与检索
# 最大数
Leetcode 179题，与剑指offer中的 把数组排成最小的数 (opens new window) 这个是类似的。
# 问题
给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。
示例 1:
输入: [10,2]
输出: 210
示例 2:
输入: [3,30,34,5,9]
输出: 9534330
2
3
4
5
6
7
说明: 输出结果可能非常大，所以你需要返回一个字符串而不是整数
# 思路
自定义一种comparator，s1和s2的值谁大，是根据 比较 s1s2 拼接之后和 s2s1 拼接之后两个哪个大来决定。
# 代码
class Solution(object):
def sort(self, x, y):
left, right = x + y, y + x
return 1 if left > right else -1
def largestNumber(self, nums):
if not nums:
return ""
if sum(nums) == 0: # 处理一下全都为0的特殊情况，不能返回“00000”这样的结果
return "0"
str_list = [str(n) for n in nums]
str_list.sort(self.sort, reverse=True)
return "".join(str_list)
2
3
4
5
6
7
8
9
10
11
12
13
# 摆动排序 II
Leetcode 324题
# 问题
给定一个无序的数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。
示例 1:
输入: nums = [1, 5, 1, 1, 6, 4]
输出: 一个可能的答案是 [1, 4, 1, 5, 1, 6]
示例 2:
输入: nums = [1, 3, 2, 2, 3, 1]
输出: 一个可能的答案是 [2, 3, 1, 3, 1, 2]
2
3
4
5
6
7
说明: 你可以假设所有输入都会得到有效的结果。 你能用 O(n) 时间复杂度和原地 O(1) 额外空间来实现吗？
# 思路
先整个排序，然后将数组分成前后两半，从后往前取，每一半里取一个。
例如[3,4,4,5]分成 [3,4] [4,5]，这里要注意必须是从后往前取，得到 4534，abcd位置保证了b大于a，a大于c所以b也大于c，如果是从前往后取就是3445，abcd位置中只能保证b大于a，但是c大于a，不能保证b和c的关系。
# 代码
本题由于题目中要求原地返回，可按下面的写法，先排序，然后直接利用python的列表赋值，两行搞定也是666啊。
class Solution(object):
def wiggleSort(self, nums):
"""
:type nums: List[int]
:rtype: None Do not return anything, modify nums in-place instead.
"""
nums.sort(reverse=True)
nums[::2], nums[1::2] = nums[len(nums)//2:], nums[:len(nums)//2]
2
3
4
5
6
7
8
# 寻找峰值
Leetcode 162题
# 问题
峰值元素是指其值大于左右相邻值的元素，例如 142 的峰值就是4。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。你的解法应该是 O(logN) 时间复杂度的。你可以假设 nums[-1] = nums[n] = -∞（数组两端的值是负无穷，也就是说加入数组只有14的话4也是峰值）。
# 思路
直接遍历一遍倒是容易想到，但是复杂度是o(n)。看到 log n 的要求，那必然是要通过逐层二分来搞。
有这样的规律，先通过二分找到中间位置i，如果nums[i] > nums[i+1]，则在i之前一定存在峰值元素，如果nums[i] < nums[i+1]，则在i+1之后一定存在峰值元素。
为什么呢？假如说 nums[i] > nums[i+1] 吧，那如果 nums[i-1] 比 nums[i] 小的话，那说明 i 位置的就是峰值；如果比nums[i]大的话，那么再继续往前找，如果 nums[i-2] 比 nums[i-1] 小的话，那么 i-1 位置的就是峰值，否则仍然继续往前找。如果一直都逐个递增的话，题目中已经给出了数组两边边界的数是无穷小的，那么就是边界值是峰值。综上，二分查找较大的那一半一定会有峰值元素。
# 代码
class Solution(object):
def findPeakElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l, r = 0, len(nums) - 1
while l < r:
mid = l + (r - l) // 2
if nums[mid] > nums[mid + 1]:
r = mid
else:
l = mid + 1
return l
2
3
4
5
6
7
8
9
10
11
12
13
14
# 寻找重复数
Leetcode 287题
# 问题
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例 1:
输入: [1,3,4,2,2]
输出: 2
示例 2:
输入: [3,1,3,4,2]
输出: 3
2
3
4
5
6
说明： 不能更改原数组（假设数组是只读的）。 只能使用额外的 O(1) 的空间。 时间复杂度小于 O(n^2) 。 数组中只有一个重复的数字，但它可能不止重复出现一次。
# 思路
由于本题不能使用额外n的空间，也不能修改原数组，一些比较常规的想法似乎就不太可行了。这个题竟然可以转化成求 链表里环的入口 (opens new window) ！！
我们把每个位置的数字看作是一个指针，代表下一个位置的下标，按照数字作为轨迹来在数组中游走，由于重复数字的出现，这个链表中是有环的。（由于数字都在1到n之间，数组长度n+1，我们把数字当作下标来看待，下标从0开始标，在数组中游走，不会发生越界）
# 代码
class Solution(object):
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
slow, fast = 0, 0
# 先让两指针相遇，相遇时slow走过的距离就是环的长度
while slow != fast or fast == 0:
slow = nums[slow]
fast = nums[nums[fast]]
# slow从头再走，fast继续走，相当于fast比slow提前走了环长步，二者再次相遇时就是环的入口
slow = 0
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 计算右侧小于当前元素的个数
Leetcode 315题
# 问题
给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
示例:
输入: [5,2,6,1]
输出: [2,1,1,0]
解释:
5 的右侧有 2 个更小的元素 (2 和 1).
2 的右侧仅有 1 个更小的元素 (1).
6 的右侧有 1 个更小的元素 (1).
1 的右侧有 0 个更小的元素.
2
3
4
5
6
7
8
# 思路
暴力n^2解法就是每一个都去把它右边扫一遍，容易想到，但是据说测试用例里有10万多长度的数组，暴力肯定是要超时了。
可以借助二叉搜索树（左子树的所有节点都小于根，右子树都大于根），树的每个节点中都记录它的左子树的节点个数count（也即小于它的元素的个数）。
要做的就是实现这样一棵树，构建时我们从右往左，逐个新加入节点。这是因为从右往左的话，每个元素右边的元素已经在树里了，所以直接取count就是小于它的元素个数。
# 代码
# 定义树节点
class TreeNode(object):
def __init__(self, val):
self.left = None
self.right = None
self.val = val
self.count = 0
class Solution(object):
def countSmaller(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
length = len(nums)
root = None
res = [0 for _ in range(length)] # 保存结果
for i in reversed(range(length)): # 要从右往左处理！
root = self.insertNode(root, nums[i], res, i)
return res
def insertNode(self, root, val ,res, res_index):
if not root:
root = TreeNode(val)
elif val <= root.val:
root.count += 1 # 值比根小，则放到左子树，根的count+1。继续在左子树中寻找
root.left = self.insertNode(root.left, val, res, res_index)
elif val > root.val: # 值比根大，放到右子树，此时已知根以及根的左子树都比val小，所以下一行中 res[res_index] 要先累加上左子树的个数 count 以及 1（根）
res[res_index] += root.count + 1
root.right = self.insertNode(root.right, val, res, res_index)
return root
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# 动态规划
# 至少有K个重复字符的最长子串
Leetcode 395题
# 问题
找到给定字符串（由小写字符组成）中的最长子串 T ， 要求 T 中的每一字符出现次数都不少于 k 。输出 T 的长度。
示例 1:
输入:
s = "aaabb", k = 3
输出:
3
最长子串为 "aaa" ，其中 'a' 重复了 3 次。
示例 2:
输入:
s = "ababbc", k = 2
输出:
5
最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。
2
3
4
5
6
7
8
9
10
11
12
13
# 思路
乍一看真的是无从下手呢。核心思路是，如果某个字符x出现次数小于k，那包含它的子串一定不符合要求，所以我们可以用x作为分界点，切分字符串，并且继续对各个子串递归下去。如果一个子串中所有字符的出现次数都大于k，那说明这个子串符合要求，返回其长度。
# 代码
分享一个leetcode看来的简洁的代码，真的是6啊。
class Solution(object):
def longestSubstring(self, s, k):
if not s:
return 0
for c in set(s):
if s.count(c) < k: # 有小于k的，则以它为基准来切分，各个子串递归下去
return max(self.longestSubstring(t, k) for t in s.split(c))
# 都大于k，则返回子串长度
return len(s)
2
3
4
5
6
7
8
9
# 二叉树中的最大路径和
Leetcode 124题
# 问题
给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
输入: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
输出: 42 （ 15 - 20 - 7 这条路径）
2
3
4
5
6
7
8
9
# 思路
对每个点，我们可以计算其maxgain，也就是把节点自身以及它的两个孩子的maxgain加在一起所得到的最大和。
所以就可以按照这个思路递归下去。在递归的过程中，维护一个全局的 max_sum 标记当前全局最大路径和，对每个节点，如果其maxgain大于最大路径和，则更新max_sum。（注意更新max_sum是要在节点的左右孩子递归完成之后才更新）
# 代码
class Solution:
def __init__(self):
import sys
self.max_sum = -1 * sys.maxint
def maxPathSum(self, root):
self.max_gain(root)
return self.max_sum
def max_gain(self, node):
if not node:
return 0
left_gain = max(self.max_gain(node.left), 0)
right_gain = max(self.max_gain(node.right), 0)
self.max_sum = max(self.max_sum, node.val + left_gain + right_gain)
return node.val + max(left_gain, right_gain)
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 最长连续序列
Leetcode 128 题
# 问题
给定一个未排序的整数数组，找出最长连续序列的长度。要求算法的时间复杂度为 O(n)
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
2
3
# 思路
按照官方题解的思路总结一下
1）暴力法 因为是整数数组，把每个元素当作序列的最小数字，让它一直加1，并且在数组中查找+1之后的数是否存在，直到不存在，则这个长度就是以该元素开头所能找到的最长连续序列。把每个元素都找一遍之后取最长就可以。
如果查找的复杂度是o(n)的话，暴力法最外层循环n个数字，中间层对数字不断+1的复杂度为n，查找复杂度也是n，那么达到了n3的复杂度。
2）排序 先把数组排序，然后从头到尾开始找，如果数字i与他之前的数字相等则不作处理继续找，如果不等则说明断裂，记下当前的长度并更新最大长度，然后以当前数字i为开头继续往后找。
排序用到的复杂度是 nlogn，后续从头到尾找的复杂度是n，所以最终复杂度是 nlogn ，还是没有达到题目复杂度 n 的要求。
3）哈希表和线性空间的构造 上面暴力法其实可以优化下，例如在查找数字是否存在在列表中时，借助哈希表可以实现o（1）复杂度的查询。同时，并不把每个元素都当作序列的最小数字了，只把 值-1 不在列表中的当作起始数字（因为 值-1 在列表中的话，我们把 值-1 这个数字当作起始数字的时候，当前 值 已经算在序列里头了，这个序列也肯定不是最长序列）。
emmm我感觉这个还是n^2的，外层的执行次数k是列表里包含了多少个序列的数量，k应该和n的长度是有关联的吧（n越大，列表里可能会包含更多个序列）但是官方说复杂度是n.
# 代码
代码写起来并不复杂，关键是要想到这种思路（找到序列起始元素，并且以每个起始元素不断+1来找后续的长度）。
class Solution(object):
def longestConsecutive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
s = set(nums)
ret = 0
for n in nums:
if (n - 1) not in s:
# 找到一个起始点
l = 1
t = n + 1
while t in s:
t += 1
l += 1
if l > ret:
ret = l
return ret
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 打家劫舍
Leetcode 198题
# 问题
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:
输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
2
3
4
5
6
7
8
9
10
11
# 思路
dp 方程 dp[i] = max(dp[i-2]+nums[i], dp[i-1]) 从左到右处理。对于第i间房子，要么取i，那么i-1的就肯定不能取了，所以此时打劫的收益是dp[i-2]+nums[i]，要么不取i，那么此时可以取 i-1（当然实际取不取咱不管），计算打劫的收益就是dp[i-1]，两者取较大的，就是第i间房子时的收益。
1、2间房子的情况需要单独处理下，之后的都可以用前面的公式来搞了。
# 代码
下面代码中p相当于i-2的收益，q相当于i-1的收益，效率很高，超过90%的python！
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l = len(nums)
if l == 0:
return 0
if l == 1:
return nums[0]
p = nums[0]
q = max(nums[0], nums[1])
for i in range(2, l):
next_ = max(p + nums[i], q)
p, q = q, next_
return q
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 完全平方数
Leetcode 279题
# 问题
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例 1:
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.
示例 2:
输入: n = 13
输出: 2
解释: 13 = 4 + 9.
2
3
4
5
6
7
8
9
# 思路
一开始能想到的一种思路：找出N最接近的平方数，再循环找出剩余最接近的平方数集合，例如12 = 9 + 1 + 1 + 1，但这样显然不是最短的结果，如果把所有情况都求出来的话，效率就会比较低。
动态规划：dp方程为，总和为 n 的最小完全平方数个数 = min(总和为 (n - 某个完全平方数) 的最小完全平方数个数) + 1
图论：将整个问题变成一个图论问题，从n到0每个数字代表一个节点，如果两个数字之间相差了一个完全平方数，则在它们之间连一条边，就得到了一个无权图，问题转化为在这个无权图中，找到n到0的最短路径，可以使用BFS来完成
拉格朗日四平方定理：任何一个正整数都可以表示成不超过四个整数的平方之和，另外有一个推论，满足四数平方和定理的数n，必定满足 n=4^a(8b+7)。
# 代码
以上的三种思路，依次搬运下代码过来吧。
先搬运一个（3）的。按照四平方和定理及其推论，一个数字如果含有因子4，那么可以把4都去掉不影响结果；如果一个数除以8余7的话则它一定由4个完全平方数组成。具体咋证明的先不能深究了。所以有了下面的代码：
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
# 通过两个步骤来缩小该数
while n % 4 == 0:
n /= 4
if n % 8 == 7:
return 4
# 再通过循环遍历，判断缩小后的数，是否可以由一个数的平方或者两个数的平方的和组成
a = 0
while a**2 <= n:
b = int((n - a**2)**0.5)
if a**2 + b**2 == n:
if a != 0 and b != 0:
return 2
else:
`return 1
a += 1
# 不行的话，返回3
return 3
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
再来一个思路（2）的，图论BFS。不过先简单说一下BFS算法的思路，首先选择一个节点为起始节点，将它做标记，并放入队列；从队列取出首部的节点，访问它，同时将它的所有未被标记过的邻接节点做标记，并放入队列；依次重复步骤，直到队列为空。
from queue import Queue
class Solution:
def numSquares(self, n: int) -> int:
around = []
for i in range(1, n + 1):
if i**2 <= n:
around.append(i**2)
else:
break;
r = 0
seen = set() # 防止重复运算
# ----------------BFS 开始----------------------
# 初始化根节点
q = Queue()
q.put((0, r))
# 进入队列循环
while not q.empty():
# 取出一个元素
cur, step = q.get()
step += 1
# 放入周围元素
for a in around:
a += cur
if a == n:
return step
if a < n and (a, step) not in seen:
seen.add((a, step))
q.put((a, step))
# ----------------------------------------------
return 0
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
再来一个DP的：
class Solution(object):
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
max_num = int(math.floor(n ** 0.5))
# 列出符合条件的完全平方数
nums = [i*i for i in range(1, max_num + 1)]
dp = dict()
dp[0] = 0
dp[1] = 1
for i in range(1, n + 1):
count = float('inf')
for num in nums:
if i - num >= 0:
count = min(count, dp[i - num] + 1)
else:
break
dp[i] = count
return dp[n]
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 最长上升子序列
Leetcode 300题
# 问题
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
2
3
4
说明: 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。 你算法的时间复杂度应该为 O(n2) 。 进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
# 思路
本题的子序列，不要求连续。而且上升要求严格递增，例如2334连续有两个3相等就不行。
1）动态规划
(题解写的太赞了，这里直接搬运过来。)
定义状态：dp[i] 表示以第 i 个数字为结尾的最长上升子序列的长度。即在 [0, ..., i] 的范围内，选择 以数字 nums[i] 结尾 可以获得的最长上升子序列的长度。注意：以第 i 个数字为结尾，即 要求 nums[i] 必须被选取。反正一个子序列一定会以一个数字结尾，那我就将状态这么定义，这一点是常见的。
状态转移方程：遍历到索引是 i 的数的时候，我们应该把索引是 [0, ... ,i - 1] 的 dp 都看一遍，如果当前的数 nums[i] 严格大于之前的某个数，那么 nums[i] 就可以接在这个数后面形成一个更长的上升子序列。把前面的 i 个数都看了，dp[i] 的值就是它们的最大值加 1。即比当前数要小的那些里头，找最大的，然后加 1 。
状态转移方程：dp(i) = max( 1 + dp(j) if j < i and dp[i] > dp[j])。
最后不要忘了，扫描一遍这个 dp 数组，其中最大值的就是题目要求的最长上升子序列的长度。
- 二分查找+贪心算法
思路是这样的，维护一个递增的数组，遍历nums，当出现的数i大于这个数组尾部的数（即数组中最大的数），则直接append到最后。当出现的数i小于等于数组中的某个数时，我们通过二分查找的方式，在数组中找到比i大的最小的数，用i替换它，其他元素不变。最后，数组的长度就是最长上升子序列的长度。
做示例如下：
3 5 6 2 5 4 5 19 5 6 7 12
[]
append 3 [3]
append 5 [3, 5]
append 6 [3, 5, 6]
2 replace 3 [2, 5, 6]
5 replace 5 [2, 5, 6]
4 replace 5 [2, 4, 6]
5 replace 6 [2, 4, 5]
append 19 [2, 4, 5, 19]
5 replace 5 [2, 4, 5, 19]
6 replace 19 [2, 4, 5, 6]
append 7 [2, 4, 5, 6, 7]
append 12 [2, 4, 5, 6, 7, 12]
max length = 6
2
3
4
5
6
7
8
9
10
11
12
13
14
15
按照上面的流程走一遍，大概也能明白这样做的思路。遇到大的数当然可以直接append，使得最长长度扩充了。遇到小的数，我们为它寻找一个位置，它之前比它小的那一部分长度仍然将可以继续利用，它之后比它大的元素可以继续接在它后面，如果有更长的上升子序列，数组的长度也会被扩充，如果没有，数组不会缩短，仍然保有了之前的最长长度。
# 代码
动态规划的代码，两层循环，复杂度是 n^2
class Solution:
# 将 dp 数组定义为：以 nums[i] 结尾的最长上升子序列的长度
# 那么题目要求的，就是这个 dp 数组中的最大者
# 以数组 [10, 9, 2, 5, 3, 7, 101, 18] 为例
# dp 的值： 1 1 1 2 2 3 4 4
def lengthOfLIS(self, nums):
size = len(nums)
# 特判
if size <= 1:
return size
dp = [1] * size
for i in range(1, size):
for j in range(i):
if nums[i] > nums[j]:
# + 1 的位置不要加错了
dp[i] = max(dp[i], dp[j] + 1)
# 最后要全部一看遍，取最大值
return max(dp)
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
二分+贪心，外层循环是n，由于内层可以采用二分查找（我们用于记录的数组一直是有序的），复杂度是 log n，这也是为什么复杂度可以降低到 nlogn。当然如果不二分查找，用顺序查找的话复杂度还是n^2了。
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
size = len(nums)
if size < 2:
return size
tail = []
for num in nums:
# 找到大于等于 num 的第 1 个数
l = 0
r = len(tail)
while l < r:
mid = l + (r - l) // 2
if tail[mid] < num:
l = mid + 1
else:
r = mid
if l == len(tail):
tail.append(num)
else:
tail[l] = num
return len(tail)
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 零钱兑换
Leetcode 322题
# 问题
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
示例 2:
输入: coins = [2], amount = 3
输出: -1
2
3
4
5
6
7
8
说明: 你可以认为每种硬币的数量是无限的。
# 思路
这个题其实和上面的“完全平方数”还是挺相似的hhhhh。
- 动态规划 关于动态规划，可以参考这个题解，说的比较清晰易懂了！ https://leetcode-cn.com/problems/coin-change/solution/dong-tai-gui-hua-tao-lu-xiang-jie-by-wei-lai-bu-ke/
简单总结下上面题解里的说法，以斐波那契来类比，如果我们从n开始 f(n) = f(n-1) + f(n-2) 这样，其实是很暴力的，重复算了很多次 f(1) f(2) f(3) 之类的值，这是暴力的递归。如果我们在算到f(1) f(2) f(3) 时拿小本本记下来，之后遇到需要f(1) f(2) f(3)时先检查下小本本有没有，这叫“带备忘录”的递归，相当于节省了一些步骤。既然都有了小本本，其实可以更进一步，之前是从顶向下，现在从底向上，先算 f(1) f(2) f(3) 再依次往上，可以直接用一个循环，不用递归就能做，这也是DP的思路。
“当问题中要求求一个最优解或在代码中看到循环和 max、min 等函数时，十有八九，需要动态规划大显身手。”
既然DP最核心的是写出状态转移方程，不如尝试来把本题写一下，就以 125三种硬币为例，amount=11，f(11)代表凑够11元所需的最小硬币数量，那么可以想到，f(11) = 1 + min{ f(11-1) , f(11-2), f(11-5) } 。这就是状态转移方程啦。
其实DP类似于之前的斐波那契数列，如果我们从 n开始逐个往下拆分 n-1， n-2， 通过递归来实现，会有大量的重复计算；而如果从 0， 1， 2开始逐个往后叠加计算，则后面的计算可以利用到前面算出的值。DP也是一样，如果从11开始利用递归的方法往下计算，也会有很多重复计算，而如果从前往后，amount从1开始累加到n，就可以利用上前面的值了，效率大幅提高。
2）图的BFS，找到一条0到amount的最短路径
# 代码
import sys
class Solution(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
dp = [sys.maxint] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for c in coins:
if c <= i:
dp[i] = min(dp[i], dp[i - c] + 1)
return -1 if dp[amount] > amount else dp[amount]
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 矩阵中的最长递增路径
Leetcode 329 题
# 问题
给定一个整数矩阵，找出最长递增路径的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。
示例 1:
输入: nums =
[
[9,9,4],
[6,6,8],
[2,1,1]
]
输出: 4
解释: 最长递增路径为 [1, 2, 6, 9]。
2
3
4
5
6
7
8
9
# 思路
1） DFS+记忆矩阵的方式 从点i出发的最长递增路径，其实是 1 + max { 从 比i的值大的i的邻居 出发的最长递增路径 }，所以通过一个记忆矩阵外加深度优先可以搞定。具体见下面的代码。
- DP 以下面的矩阵为例，如果从头到尾来处理，在处理1的时候需要先拿到2的dfs，而要拿2的dfs有需要先拿3的dfs，递归的层数还是比较深的。好在借助了记忆矩阵，每个点的dfs只需要算一次。这其实就是那个讲动态规划的题解里说的“带备忘录的递归”啊，可以想办法从底向上来做，就避免了递归。
1 2 3
2 3 4
3 4 5
2
3
如果我们先从5开始，由于5的邻居都比它小，那么5的dfs值就是1；再从4开始，比4大的邻居只有5，5已经算出来了是1，所以4的dfs是2，依次类推。所以发现，按照从大到小的顺序来处理，可以避免递归，实现“动态规划”。
# 代码
1）搬运一个c++版的代码，展示DFS+记忆矩阵的思路。
# dfs函数，给定一个点，返回从该点出发的最长递增路径
int dfs(vector<vector<int>> &matrix, vector<vector<int>> &memo, int x, int y){
if(memo[x][y]!=-1) return memo[x][y]; # 如果memo中已经有结果了，直接返回即可， -1代表没有结果
int dirs[] = {0, -1, 0, 1, 0};
int ans = 1;
for(int i=0; i<4; i++){ # 通过dirs代表上下左右四个方向，挨个探索邻居
int tx = x+dirs[i], ty = y+dirs[i+1];
if(tx<memo.size() && tx>=0 && ty>=0 && ty<memo[0].size() && matrix[x][y]>matrix[tx][ty]){ # 未越界，并且是比当前xy点的值大的邻居
ans = max(ans, 1+dfs(matrix, memo, tx, ty)); # 根据邻居的最长递增路径，更新当前点的最长递增路径
}
}
}
return memo[x][y]=ans; # 更新memo
}
int longestIncreasingPath(vector<vector<int>>& matrix) {
int m = matrix.size(); if(m==0) return 0;
int n = matrix[0].size(); if(n==0) return 0;
vector<vector<int>> memo(m, vector<int>(n, -1)); #初始化memo
int ans = 1;
# 对每个点进行搜索，ans记录最长值
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
ans = max(ans, dfs(matrix, memo, i, j));
}
}
return ans;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
2） 搬运一个python代码。首先将各个点的值和坐标加入列表中，按其值从大到小排序，然后按照这个顺序取用坐标，访问各个点。在访问每个点时，比它大的邻居的值肯定已经算出来了，直接取用即可。
class Solution(object):
def longestIncreasingPath(self, matrix):
if not matrix or not matrix[0]:
return 0
m, n = len(matrix), len(matrix[0])
lst = []
for i in range(m):
for j in range(n):
lst.append((matrix[i][j], i, j))
lst.sort()
dp = [[0 for _ in range(n)] for _ in range(m)]
for num, i, j in lst:
dp[i][j] = 1
for di, dj in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
r, c = i + di, j + dj
if 0 <= r < m and 0 <= c < n:
if matrix[i][j] > matrix[r][c]:
dp[i][j] = max(dp[i][j], 1 + dp[r][c])
return max([dp[i][j] for i in range(m) for j in range(n)])
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
哈哈DP这块终于暂告段落了，虽然刷起来很吃力，但是也算对DP有了基本的了解啦，以后遇到DP的题也可以尽力尝试自己做一下。