LeetCode

题解 - Solutions

数组与字符串 - Array and Strings

1. Two Sum

• 描述

  给定一个整型数组和一个目标数，返回整型数组中两个数的和为目标数的下标（题目保证有解，数组中每一个数只能使用一次。

• 题解

  初始化字典dic，其键值为数组中某元素与其下标，遍历数组中每个元素arr[i]，目标值target与arr[i]的差记为diff，在dic中查找键diff，如果存在，则返回diff的下标与i，如果不存在，为dic建立arr[i]与i的键值对。

125. Valid Palindrome

• 描述

  给定一个字符串，判断该字符串是否是回文串。回文串是从前后方向阅读都相同的串。

• 题解

  同时从字符串正序、逆序遍历字符串，如果所有字符都相同，则是回文串，否则不是回文串。

8. String to Integer

• 描述

  给定一个字符串，字符串可能包含非数字字符，例如字母和符号。如果以负号以外的非数字开头，则返回0，否则将字符串数字，含符号，转化为32位整型。

• 题解

  略。

344. Reverse String

• 描述

  给定一个字符串，将字符串逆置。

• 题解

  同时从字符串的正序、逆序遍历字符串，交换两个字符的位置，直到两下标相等。

20. Valid Parentheses

• 描述

  给定一个字符串表达式，判断表达式中的括号是否合法，一个合法的括号应该像：{[()]}，这样的形式。

• 题解

  维护一个栈，记作stack，然后遍历字符串，如果遇到左括号字符，则将该字符入栈，如果遇到右括号字符，则将栈顶出栈，判断括号是否匹配，如果匹配失败，则返回False，如果匹配成功，则继续遍历直到结束。如果遍历结束，栈不为空，则匹配失败，否则匹配成功。

5. Longest Palindromic Substring

• 描述

  给定一个字符串，返回这个字符串的最大回文子串。

• 题解

  由于枚举所有长度的子串，并判断该子串是否是回文子串的复杂度（O(n * m * m)）过高，故考虑动态规划。在外层循环以下标j遍历字符串下标，j代表了子串的右界（0 <= j <= len(s)），内层循环以下标i遍历子串下标（0 <= i <= j），易知，当j=i时，原字符串s的子串sub_s，即s[i:j+1]是回文的，而当j-i=1时，如果s[i]=s[j]则子串sub_s，是回文的，而当j-i>1时，子串sub_s是否回文，取决于是否s[i]=s[j]且s[i+1:j-1]是否为真，如果为真，则sub_s回文。所以，我们维护一个dp二维数组，其下标i,j表示原字符串从下标i开始到j结束（包含j）的子串是否为回文子串。在便利过程中不断更新最长的下标i, j最后返回最长回文子串。

49. Group Anagrams

• 描述

  给定一个字符串型数组，将具有相同字符组成的字符串分别保存为一个字符串型数组，返回一个字符串型数组型的数组，作为结果。

• 题解

  维护一个字典记作dic，其键值分别为按字典序排序后的字符串和字符串型数组。遍历字符串型数组，对每一个字符串s，按字典序排序，结果记作s_sorted，在dic中取s_sorted的值res，res是一个字符串型的数组，然后将s添加进res，最后返回dic的values作为结果。

42. Trapping Rain Water

• 描述

  接雨水，给定一个整型数组height，数组内每个元素的值代表了“墙”的高度，墙的高度差可以用来储水，求给定一组墙高，能储多少水。

• 题解

  首先遍历height，找到最高“墙”的下标i_max_height，初始化一个i_cur_peak=0代表当前“左高峰”，然后从左到i_max_height遍历墙高，期间，如果当前“左高峰”小于当前墙高，则更新“左高峰”，否则，更新雨水总量rain+=i_cur_peak-height[i]，即“左高峰”减去当前墙高，直到遍历到墙的最高处为止。然后从右到i_max_height遍历墙高，逻辑同上。最后返回雨水总量。

15. 3Sum

• 描述

  给定一个整型数组num，例如[-1, 0, 1, 2, -1, -4]，返回一组结果，每个结果是一个数组，满足：在nums中选3个数字，这3个数字的和为0，过滤重复解。

• 题解

  首先，3个数字a, b, c的和为0，即a + b = c，则将问题转化为了一个Two Sum问题，所以，我们先排序数组nums，并初始化targets数组：[-num for num in nums]。以下标i进入循环，初始化y_map与target = targets[i]，y_map用来记录是否y已经查找过。然后遍历nums[i + 1:]的每一个元素x，将target - x记作y，如果y在y_map中，则添加结果-target, x, y作为一个解。否则，y_map[x] = x，记录当前x到y_map字典中。最后去重结果并返回。

48. Rotate Image

• 描述

  给定一个二维数组matrix，将它顺时针旋转90°，不可以申请新空间。

• 题解

  首先，将matrix转置，以i, j为行列，进入循环，即对于每一个元素matrix[i][j] = matrix[j][i]，需注意，此处j从i开始，因为只需遍历matrix的上三角矩阵即可。然后，再将转置的矩阵martix水平翻转，即以i, j为行列进入循环，使得matrix[i][j] = matrix[i][num_col - j - 1]，需要注意，j的上界是num_col // 2，因为num_col // 2为轴心。

66. Plus One

• 描述

  给定一个数组nums，如[1, 2, 3]，代表了123的各位，现在对个位加一，返回结果数组，如[1, 2, 4]。

• 题解

  初始化carry进位标识符，首先对个位加一，如果结果大于10，则模10后标记carry = 1，然后遍历剩余的位数加carry，同时判断是否进位，直到遍历结束。如果遍历结束后carry = 1，则插入1到数组下标为0处。

189. Rotate Array

• 描述

  给定一个数组nums，与一个整数k，代表将前k位数移至数组末尾，就地修改数组nums。

• 题解

  以下标i进入循环，循环执行k次，每次nums.insert(nums.pop(0)即可。

215. Kth Largest Element in an Array

• 描述

  给定一个数组记为nums，返回第k大的元素。

• 题解

  首先通过heapq.heapify(nums)建堆，然后通过heapq.nlargest(k, nums)[-1]返回结果即可。

76. Minimum Window Substring

• 描述

  给定原始字符串s与目标字符串t，返回一个最小窗口字符串sub_s，该窗口字符串是最小的字符串包含了目标字符串t所有字符。

• 题解

  首先初始化两个字典记作start_dic和end_dic，它们的键值分别为字符和出现的次数，然后遍历t中的每一个字符，更新这两个字典。然后计算t的长度记为t_length。初始化下标start = 0，然后以end = 0为下标遍历s，end表示s的右边界，如果s[end]在end_dic中，而且end_dic[s[end]] > 0，则将start_dic[s[end]]自减，同时，如果start_dic[s[end]] >= 0，则将t_length自减，如果t_length == 0，则进入以下循环：如果s[start]在end_dic中，而且end_dic[s[start]] > 0，如果start_dic[s[start]] < 0则start_dic[s[start]]自增，否则break，start += 1，然后根据当前最小窗口大小min_size是否大于end - start + 1来更新最小窗口大小min_size，和结果起始下标min_start。最终，如果min_size < len(s) + 1，则返回s[min_start: min_start + min_size]，否则返回空串。

链表 - Linked List

206. Reverse Linked List

• 描述

  给定一链表，将它就地逆序。

• 题解

  初始化前驱节点pre_node=None，通过head_node遍历链表，通过cur_node临时存储head_node，然后更新head_node = head_node.next，接着更新当前节点的后继节点为前驱节点，cur_node.next = pre_node，最后将前驱节点更新为当前节点，pre_node = cur_node，直到遍历结束，最终返回pre_node为逆序后的头结点。

141. Linked List Cycle

• 描述

  给定一个链表，判断链表是否存在“环”

• 题解

  分别维护快慢指针，初始化为s_node, f_node = head, head.next，以快慢指针都为真的条件进入while循环，如果快指针与慢指针地址相等，则存在环，否则更新慢指针，s_node=s_node.next，更新快指针两次，f_node=f_node.next，if f_node: f_node = f_node.next，继续循环，如果循环结束，则不存在环。

2. Add Two Numbers

• 描述

  给定两个链表，它们从头节点到尾节点分别表示数字的最低位到最高位，求将两链表相加的结果链表。

• 题解

  初始化进位记录标识符count=0与结果头节点head，以两链表为真的条件进入循环，将当前节点结果相加，并加count后，模10，如果进位，则将count记为1，并保存结果cur_node.next = Node(x)，然后更新cur_node=cur_node.next，直到循环结束。如果仍有较长链表遍历未结束，则遍历该链表，依次将其节点与count相加后添加在结果节点的cur_node后，直到遍历结束，最后检查进位是否需要需要创建新节点，并返回结果头节点。

21. Merge Two Sorted Lists

• 描述

  给定两个有序链表，将他们合并成新的有序链表，并返回这个链表的头节点。

• 题解

  初始化新头节点与当前节点记为head_node与cur_node，以两链表为真的条件进入循环，比较两链表的当前值，将值小的节点添加为cur_node的后继节点，然后更新该节点为之后继，然后更新cur_node=cur_node.next，直到循环结束。循环结束后，如果仍有链表为真，则将剩余部分作为cur_node的后继，然后返回头节点。

23. Merge k Sorted Lists

• 描述

  给定k个有序链表，将他们合并成新的有序链表，并返回这个链表的头节点。

• 题解

  同上，略。

树和图 - Trees and Graphs

98. Validate Binary Search Tree

• 描述

  给定一个树，判断该二叉树是否是二叉查找树

• 题解

  将中根遍历该二叉树的结果保存，检查该数组是否有序，如果有序，则是二叉查找树。

94. Binary Tree Inorder Traversal

• 描述

  给定一颗二叉树，输出中根遍历结果。

• 题解

  初始化栈stack，将元组(root, False)入栈，以栈不为空进入循环，将栈顶元组出栈，结果记为cur_node, visited，如果cur_node为真时，visited为真，即已经访问了该节点，则将该节点的值cur_node.val添加到结果数组，如果visited为假，即尚未访问该节点，则依次将该节点的右节点，该节点，该节点的左节点入栈，他们的访问标记分别为False, True, False，然后继续循环。最后打印结果。

102. Binary Tree Level Order Traversal

• 描述

  给定一颗二叉树，输出层序遍历结果。

• 题解

  初始化层节点数组level_nodes=[root]，以层节点数组不为空为条件进入循环，向结果数组添加层节点数组内所有节点的值，然后初始化临时层节点数组tmp_level_nodes，遍历当前层节点的所有节点，添加他们的左右孩子节点（需为真），然后更新level_nodes=tmp_level_nodes，直到循环结束，最后返回结果数组。

103. Binary Tree Zigzag Level Order Traversal

• 描述

  给定一颗二叉树，输出层序遍历结果，双数层的结果逆序。

• 题解

  同上，在更新双数层节点时逆序即可，略。

116. Populating Next Right Pointers in Each Node

• 描述

  给定一颗满二叉树，将二叉树的每一层变成一个链表（二叉树的节点数据结构已经有next成员变量）

• 题解

  同上，在更新level_nodes==tmp_level_nodes后，遍历之，node.next = next_level_nodes[index + 1]更新后继节点。

117. Populating Next Right Pointers in Each Node II

• 描述

  给定一颗二叉树，将二叉树的每一层变成一个链表（二叉树的节点数据结构已经有next成员变量）

• 题解

  同上，略。

235. Lowest Common Ancestor of a Binary Search Tree

• 描述

  给定一颗二叉搜索树与其两个节点，返回这两个节点的最小公共祖先。

• 题解

  利用二叉搜索树性质并递归，如果两个节点的值pval, qval都小于root.val，那么公共祖先一定在root节点的左子树中，所以递归调用当前函数，根节点，即二叉查找树为root.left。相反，如果pval, qval都大于root.val，则公共祖先一定在root节点的右子树中，执行上述操作。最终，如果qval < root.val < pval，则root为最小公共祖先。

236. Lowest Common Ancestor of a Binary Tree

• 描述

  给定一颗二叉树与其两个节点，返回这两个节点的最小公共祖先。

• 题解

  初始化p_path, q_path分别保存先根遍历到p, q节点的路径。路径是指使用先根遍历，遍历该二叉树，直到某个节点的值等于目标节点的值node.val==target.val，并将完成标记flag=Ture，并将其他遍历结果移出路径，如何保存路径，请参见257. Binary Tree Paths。然后遍历两个路径p_path, q_path，最后一个相同的节点，即是最小公共祖先。

105. Construct Binary Tree from Preorder and Inorder Traversal

• 描述

  已知一颗二叉树的先根和中根遍历结果，恢复二叉树。

• 题解

  利用递归，以中根遍历结果数组不为空的条件进入函数，将先根数组pre_vals的首个节点值root_val出队列，并求出root_val在中根遍历数组中的下标，记为root_index，易知，中根遍历数组中，该节点下标左边的值均为其左子树的值，该下标右边的值均为其右子树的值。创建节点root=TreeNode(root_val)，而root.left则递归本函数，入参分别为pre_vals与in_vals[: root_index]，而root.right则递归本函数，入参分别为pre_vals与in_vals[root_index + 1:]，最后返回根节点。

200. Number of Islands

• 描述

  描述较为复杂，概述为寻找一个0-1矩阵中“孤岛”，即1构成的块的个数。

• 题解

  维护一个visited数组，描述了某个下标i, j是否已经访问过，以下标i, j分别代表行列遍历图，如果图中grid[i, j] == 1，则进行深度优先遍历，需注意深度优先遍历的条件，即0<=i<=row, 0<=j<=col。如果i, j已经访问过，或者grid[i, j]==0则返回0，否则将本次遍历区域加1，并将visited[i, j]=1后，继续遍历，方向为上、下、左、右。最后以所有行列i, j为入口遍历完毕后，返回累计结果。

257. Binary Tree Paths

• 描述

  给定一颗二叉树，输出先根遍历到所有叶子节点的路径字符串。

• 题解

  初始化临时路径path与结果路径集合paths，先根遍历二叉树，遍历的过程中，每访问一个节点，如果该节点为空，则返回，否则将其添加到临时路径path中，并检查该节点是否有左右孩子节点，如果没有，则执行一次path临时路径到结果路径的序列化，结果添加到paths中。如果有左右孩子节点，则继续对该节点的左右孩子进行先根遍历。如果访问到叶子节点，则对path执行pop操作，将该节点出栈。最后返回结果路径集合paths。

695. Max Area of Island

• 描述

  给定一个二维数组grid，其元素为0或1，找到最大的“孤岛”，并返回其大小。

• 题解

  维护result变量记录结果，维护一个二维数组visited，vistied[i][j]描述了grid[i][j]是否已经被访问过，然后对以i, j为下标进入循环，对grid[i][j]进行深度优先遍历。在深度优先遍历时，维护一个res = 1变量，如果grid[i][j] == 0，则返回0，如果grid[i][j] == 1，才能继续遍历，同时，将visited[i][j] = 1，并将res += 1，然后进行方向为上、下、左、右的深度优先遍历。如果res > result，则更新result = res，最后返回result作为结果。

547. Friend Circles

• 描述

  给定一个二维数组M，其中元素为0或1，表示第j个人是否是第i个人的直接朋友。如果k是j的朋友，j是i的朋友，则i与k是间接朋友，它们形成了一个“朋友圈”，求M中朋友圈的个数。

• 题解

  维护一个visited数组，表示是否已经检查过第i个人的朋友圈。然后以i为第i个人的下标，进入循环，如果visited[i] == 1，即已经检查过该人的朋友圈，则continue，否则，首先将visited[i] = 1，然后初始化栈stack = [i]，准备深度优先遍历：当栈stack不为空，则栈尾出栈记作j，则以k为第k个人的下标，进入循环，如果visited[k] == 0且M[j][k] == 1，即第k个人的朋友圈尚未检查，而且j与k互为朋友，则将k入栈。当以i为下标的外部循环结束，则将res += 1，结果自增。最后返回res作为结果。

104. Maximum Depth of Binary Tree

• 描述

  给定一颗二叉树，输出二叉树的深度。

• 题解

  略，参考层序遍历二叉树，遍历时记录深度即可。

回溯 - Backtracking

17. Letter Combinations of a Phone Number

• 描述

  数字2-9中，每个数字对应电话号码上的几个字母，给定一个由2-9组成的字符串，输出所有可能的字母组合。

• 题解

  初始化结果数组result，对给定数字字符串s以及每个字符所能对应的字母，进行深度优先遍历。即，遍历数字字符串s，对每一个下标i，与其对应的数字num，查询它可能的组成字母，依次递归调用深度优先遍历函数。深度优先遍历函数有四个参数，分别是当前下标i，数字字符串s，当前组合pattern，结果数组result，直到当前下标i == len(s)时，将pattern添加到result中，并返回结果数组。

39. Combination Sum

• 描述

  给定一个整形数组，所有元素均为正数，记作candiates，给定一个目标数记作target，在candiates找到所有整数的组合，使他们的和等于target，每个元素可以使用多次。

• 题解

  首先排序candidates，然后设计深度优先遍历函数dfs(candidates, target, last_num, result, results)。即，target == 0，则添加result到结果数组results，如果target < candidates[0]，则返回。然后遍历candidate的每一个数字记作num，对每一个num，如果它大于target，则返回。如果它小于last_num，则continue，因为这个数字应该已经被遍历过了。否则，将num添加到临时result，然后递归调用dfs(candidates, target - num, num, result, results)，最后通过result.pop()当前num，全部结束后返回results。

排序和搜索 - Sorting and Searching

26. Remove Duplicates from Sorted Array

• 描述

  给定一个已经排序的数组，数组中可能有重复元素，就地移除重复元素，并返回新的数组长度。

• 题解

  初始化有序下标j == 0，以下标i = 0开始遍历排序数组nums，如果排序数组nums在有序下标j的值不等于在下标i的值，则将j += 1，并使得nums[j] = nums[i]。如果排序数组nums在有序下标j的值等于下标i的值，则什么都不做。最后返回j + 1作为结果。

88. Merge Sorted Array

• 描述

  给定两个排序后的数组a, b，其中a数组足够长，归并两个排序数组至a数组并返回。

• 题解

  从后遍历数组a, b，初始化三个下标a_i == len(a) - 1，b_i == len(b) - 1, m_i = len(a) + len(b) - 1，分别代表a的下标，b的下标，结果下标，以a_i, b_i均大于等于0进入循环，如果a[a_i] > b[b_i]，则a[m_i] = a[a_i]，然后m_i -= 1，a_i -= 1，反之同理，直到循环结束。如果b_i仍大于等于0，则说明b仍有剩余，这些数字都很小，所以以b_i大于等于0为条件进入循环，依次a[m_i] = b[b_i]，然后m_i -= 1，然后b_i -= 1，最后结束。

75. Sort Colors

• 描述

  三色排序，给定一个整型数组nums，只包含0, 1, 2三种元素，以O(n)的时间就地排序，不可使用基数排序，后返回结果。

• 题解

  初始化三个下标i == 0, j == len(nums) - 1, k == 0，分别代表左下标，右下标，当前下标。然后k < j，即当前下标小于右下标为条件进入循环，如果nums[k] == 2，则交换num[k]与num[j]的值，然后j -= 1，即右下标左移。如果nums[k] == 1，则k += 1。如果nums[k] == 0，则交换num[k]与nums[i]的值，然后i += 1, k += 1，直到循环结束。

153. Find Minimum in Rotated Sorted Array

• 描述

  给定一个有序数组nums，数组在某一位被翻转，例如：如[0, 1, 2, 3, 4] -> [3, 4, 0, 1, 2]，返回最小元素。

• 题解

  初始化三个下标i == 0, j == len(nums) - 1, mid == 0，分别代表左下标，右下标，中下标。然后以i < j为条件进入循环，计算mid = (i + j) // 2，如果nums[mid] < nums[j]，则说明区间有序，更新j = mid，继续循环。如果nums[mid] >= nums[j]，则说明区间内存在翻转，最小元素应在翻转区间，将i = mid + 1后，继续循环。当循环结束，返回nums[i]作为结果。

33. Search in Rotated Sorted Array

• 描述

  给定一个有序数组nums和目标数target，数组在某一位被翻转，例如：如[0, 1, 2, 3, 4] -> [3, 4, 0, 1, 2]，查找target，如果存在则返回其下标，否则返回-1。

• 题解

  初始化peak_i = -1, peak_num == -inf，代表最大值和其下标。遍历数组nums，找到最大值和其下标。此时，如果target大于peak_num，则返回-1。然后进行判断，如果target >= nums[0]，则在[0:peak_i + 1]区间进行二分查找，如果target < nums[0]，则target在翻转区间内，则在[peak_i + 1:]区间内进行二分查找。

74. Search a 2D Matrix

• 描述

  给定一个二维数组nums和一个目标数target，该二维数组的每个元素是严格按下标增长的。在二维数组nums查找元素target，如果存在则返回True，否则返回False。

• 题解

  初始化peak_j = 0，以nums[j][0] <= target为条件，遍历nums每行的第一个元素，记录peak_j = j，在区间行nums[j][:]进行二分查找，后返回结果。

240. Search a 2D Matrix II

• 描述

  给定一个二维数组nums和一个目标数target，该二维数组是的每一个行是有序的，每一列是有序的。在二维数组nums查找元素target，如果存在则返回True，否则返回False。

• 题解

  初始化peak_j = 0，以nums[j][0] <= target为条件，遍历nums每行的第一个元素，记录peak_j = j，以下标i遍历0行到j行，在区间行nums[i][:]进行二分查找，后返回结果。

252. Meeting Rooms

• 描述

  给定一个数组intervals，数组内的元素是一个整型二元组，表示了会议的开始和结束时间，如果会议时间有冲突，判断会议之间是否有冲突。

• 题解

  将该数组按开始时间排序后结果记为intervals，然后以i为下标遍历数组，如果intervals[i].start < intervals[i-1].end，则有冲突，返回False，否则继续循环直到结束，返回True，即没有冲突。

253. Meeting Rooms II

• 描述

  给定一个数组intervals，数组内的元素是一个整型的二元组，表示了会议的开始和结束时间，因为会议时间有可能冲突，返回最多需要的会议室数量。

• 题解

  维护一个字典interval_rooms_map，它的键是会议开始或结束时间，它的值时此刻会议室的“名义数量”，然后遍历intervals，对interval_rooms_map[interval.start] += 1，对interval_rooms_map[interval.end] -= 1，表示每个会议interval的起始时间对会议室的“名义数量”，即如果会议开始，那么占用数需要自增，如果结束，那么占用数自减。然后，获取该字典的所有键并升序排序，其结果记为keys_sorted。然后，初始化max_room = 0, cur_room = 0，代表最大会议室数量和当前会议室数量，通过key_sorted的key遍历interval_rooms_map的值，并使得cur_room += interval_rooms_map[key]，同时更新最大会议室数量max_room = max(max_room, cur_room)，最后返回max_room。

56. Merge Intervals

• 描述

  给定一个数组intervals，数组内的元素是一个整型的二元组，表示了开始和结束时间，由于时间可能重叠，返回合并后的intervals数组，例如：[[1, 3], [2, 6], [8, 10]]合并后应该为[[1, 6], [8, 10]。

• 题解

  首先以interval.start排序intervals数组，然后初始化结果数组results = [intervals[0]]，从下标为1开始遍历排序后的intervals数组，如果interval.start <= results[-1].end，即说明出现重叠，则results[-1].end = max(interval.end, results[-1].end)。否则，添加新合并区间results.append(interval)，最后返回结果。

动态规划 - Dynamic Programming

121. Best Time to Buy and Sell Stock

• 描述

  给定一个数组prices，数组内每个元素代表了某个股票某时刻的价格，选择一个时间买入，一个时间卖出，返回最大的收益。

• 题解

  初始化最大收益s_max=0，最小价格p_min=-inf，遍历prices中的每个价格price，取p_min = min(price, p_min)，然后计算当前买入价格收益profit = price - p_min，选择更新最大收益s_max=max(profit, s_max)，最后返回s_max作为结果。

53. Maximum Subarray

• 描述

  给定一个整型数组nums，返回最大的子数组的和。

• 题解

  初始化dp = [0] * len(nums)，以下标i遍历数组nums，则dp[i] = max(nums[i], nums[i] + dp[i - 1])，即以下标为i截止的子数组nums[:i+1]，它的最大 dp[i] = max(num, num + dp[i - 1])其中dp[i]为第i个下标的最大子数组和。

70. Climbing Stairs

• 描述

  给定一个n阶楼梯，一次可以爬1阶楼梯或者2阶楼梯，返回爬到n阶，有多少种爬法。

• 题解

  初始化dp = [0] * (n + 1)，dp[i]表示爬到第i阶，有多少种爬法，所以，可以写出递推式：dp[i] = dp[i - 1] + dp[i - 2]，最后，返回dp[n - 1]作为结果。

198. House Robber

• 描述

  给定一个数组nums，nums中每个下标i对应的nums[i]代表i位置财产的价值。限定不可以同时拿取两个相邻位置的财产，返回可拿取财产的最大值。

• 题解

  初始化dp = [0] * len(nums)，则有初始情况dp[0] = nums[0]，dp[1] = max(nums[0], nums[1])，dp[i]代表了当财产个数为i个时，可拿取财产的最大值，所以，可以写出递推式：dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])，最后返回max(dp[-1], dp[-2])作为结果。

152. Maximum Product Subarray

• 描述

  给定一个整型数组nums，返回最大的子数组的积。

• 题解

  初始化dp = [0] * len(nums)，dp[i]表示以nums[i]为最后一个元素的子数组的最大子数组的积。由于负数的存在，需要初始化dp_min = [0] * len(nums)和dp_max = [0] * len(nums)，dp_min[i]与dp_max[i]分别代表以nums[i]为最后一个元素的子数组的最小数组积和最大数组积。dp_min的意义在于，由于负数的存在，如果dp_min[i - 1]是一个负数，而nums[i]同样是一个负数，则dp_min[i - 1] * nums[i]将会是正数。所以我们可以写出递推式：dp[i] = max(dp_min[i-1] * nums[i], dp_max[i-1] * nums[i], nums[i])，然后更新dp_max[i] = dp[i]，dp_min[i] = min(dp_min[i-1] * nums[i], dp_max[i-1] * nums[i], nums[i])，最后返回max(dp)作为结果。

139. Word Break

• 描述

  给定一个字符串s，给定一个字符串数组wordDic，其元素是一些单词。如果s能被wordDic中的单词组合而成，则返回True，否则返回False。

• 题解

  初始化dp = [False] * len(s) + 1，dp[i]表示以s[i]结尾的子串，是否能被wordDic中的单词组合。则外循环以下标i遍历字符串s，内循环以下标j遍历i到len(s)，如果dp[i]为真，即以s[i]结尾的子串可以被wordDic中的单词组合，而且子串s[i: j+1]在wordDic中，那么dp[j + 1] = Ture，最后，返回dp[-1]作为结果。

62. Unique Paths

• 描述

  给定一个二维数组的行列m, n，从位置mat[0][0]出发，到达mat[-1][-1]，限定能向右或者向下移动，返回走法的总数。

• 题解

  初始化dp = [[1 for _ in range(0, n)] for _ in range(0, m)]，dp[i][j]表示从出发点mat[0][0]到该点的走法数量。则以下标i, j遍历行列，则可以写出递推式：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，最后返回dp[-1][-1]作为结果。

120. Triangle

• 描述

  给定一个数组triangle，triangle中的元素均为整型数组。现自顶向下在triangle中的每行选择一个数，限定在i行选择第j个数后，在i+1行选择时只能选择j, j + 1，最终使得它们的和最小，并返回结果。

• 题解

  初始化dp = [0] * (len(triangle) + 1)，dp[i]表示“自底向上”选择数字时，第i行为止最小的和。则以i为下标，倒序遍历triangle的每一行，以j为下标遍历triangle[i]每一个元素，可以写出递推式：dp[j] = traiangle[i][j] + min(dp[j], dp[j + 1])，最后返回dp[0]作为结果。

• 描述

• 题解