# coding = "utf-8"'''自顶向下构建dp递归函数自底向上构建dp数组
'''def canJump(nums):'''给定⼀个⾮负整数数组 nums，你最初位于数组的第⼀个下标，数组中的每个元素代表你在该位置可以跳跃的最⼤⻓度，判断你是否能够到达最后⼀个下标leetcode:55. 跳跃游戏input:nums = [2,3,1,1,4]output:trueinput:nums = [3,2,1,0,4]output:false思路：1.贪心算法2.3.'''n = len(nums)farthest = 0for i in range(n - 1):farthest = max(farthest, i + nums[i])if farthest <= i:return Falsereturn farthest >= n - 1def jump(nums):'''给你⼀个⾮负整数数组 nums，你最初位于数组的第⼀个位置，数组中的每个元素代表你在该位置可以跳跃的最⼤⻓度，请你使⽤最少的跳跃次数到达数组的最后⼀个位置（假设你总是可以到达数组的最后⼀个位置）。leetcode: 45. 跳跃游戏 IIinput:nums = [2,3,1,1,4]output:2思路：1. 贪心算法2.3.'''n = len(nums)jumps, farthest, end = 0, 0, 0for i in range(n - 1):farthest = max(farthest, nums[i] + i)if end == i:jumps += 1end = farthestprint(jumps)return jumpsdef canCompleteCircuit(gas, cost):'''在⼀条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。你有⼀辆油箱容量⽆限的的汽⻋，从第 i个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的⼀个加油站出发，开始时油箱为空。如果你可以绕环路⾏驶⼀周，则返回出发时加油站的编号，否则返回 -1（如果题⽬有解，该答案即为唯⼀答案）。leetcode: 134. 加油站input:gas = [1,2,3,4,5]cost = [3,4,5,1,2]output:3思路：1. 先通过判断总油耗和总油量的值是否小于0，如果小于0，则无解2. 遍历每一站的油耗和油量是否小于0，如果小于0，说明起始点需要更换为下一站3. 贪心算法'''n, s = len(gas), sum(gas) - sum(cost)if s < 0:return -1tank, start = 0, 0for i in range(n):tank += gas[i] - cost[i]if tank < 0:start += 1tank = 0# 回到0if start == n:return 0return startdef maxSubArray(nums):'''给定⼀个整数数组 nums，找到⼀个具有最⼤和的连续⼦数组（⼦数组最少包含⼀个元素），返回其最⼤和。leetcode:53. 最⼤⼦序和input:nums = [-2,1,-3,4,-1,2,1,-5,4]output:6思路：1. 以 nums[i] 为结尾的「最⼤⼦数组和」为 dp[i]2.3.'''import mathn = len(nums)if n == 0:return 0dp = [0 for _ in range(n)]for i in range(1, n):dp[i] = max(nums[i], nums[i] + dp[i - 1])res = max(dp)return resdef rob(nums):'''你是⼀个专业的⼩偷，计划偷窃沿街的房屋。每间房内都藏有⼀定的现⾦，影响你偷窃的唯⼀制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同⼀晚上被⼩偷闯⼊，系统会⾃动报警。给定⼀个代表每个房屋存放⾦额的⾮负整数数组，计算你不触动警报装置的情况下，⼀夜之内能够偷窃到的最⾼⾦额。leetcode: 198. 打家劫舍input:[1,2,3,1]output:4思路：1.2.3.'''n = len(nums)if n == 0:return 0dp = [0 for _ in range(n + 2)]for i in range(n - 1, -1, -1):dp[i] = max(dp[i + 1], nums[i] + dp[i + 2])print(dp[0])return dp[0]def rob2(nums):'''你是⼀个专业的⼩偷，计划偷窃沿街的房屋，每间房内都藏有⼀定的现⾦。这个地⽅所有的房屋都围成⼀圈，这意味着第⼀个房屋和最后⼀个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同⼀晚上被⼩偷闯⼊，系统会⾃动报警。leetcode:213. 打家劫舍 IIinput:[2,3,2]output:3思路：1. dp[i]=x  从第 i 间房子开始抢劫，最多能抢到的钱为 x2. base case: dp[n] = 0 从第n间房子开始，抢到0;从dp[n-1]=max(dp[n],num[n-1])=num[n-1]，即当前房间钱的数量3.'''n = len(nums)if n == 1:return nums[0]def robRange(nums, start, end, length):dp = [0 for _ in range(length + 1)]for i in range(end - 1, start - 1, -1):dp[i] = max(dp[i + 1], nums[i] + dp[i + 2])return dp[start]return max(robRange(nums, 0, n - 2, n),  # 取第一个而不取最后一个robRange(nums, 1, n - 1, n)  # 取第二个且取最后一个)def rob3(root):'''198. 打家劫舍（简单） 和 213. 打家劫舍 II（中等） 的扩展。这次房屋是放在⼆叉树上，计算在不触动警报的情况下，⼩偷⼀晚能够盗取的最⾼⾦额。leetcode: 337. 打家劫舍 IIIinput:[3,2,3,null,3,null,1]3/ \2   3\   \3   1output:7思路：1.2.3.'''class Rob:def __init__(self):self.memo = dict()def _rob(self, _root):if _root is None:return 0if _root in self.memo:return self.memo[_root]# 抢do = _root.valif _root.left is not None:do += self._rob(_root.left.left) + self._rob(_root.left.right)if _root.right is not None:do += self._rob(_root.right.left) + self._rob(_root.right.right)# 不抢not_do = self._rob(_root.left) + self._rob(_root.right)res = max(do, not_do)self.memo[_root] = resreturn resdef run(self, _root):return self._rob(_root)r = Rob()res = r.run(root)print(res)def lengthOfLIS(nums):'''给你⼀个整数数组 nums，找到其中最⻓严格递增⼦序列的⻓度。⼦序列是由数组派⽣⽽来的序列，例如 [3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的⼦序列。leetcode: 300. 最⻓递增⼦序列input:[10,9,2,5,3,7,101,18]output:4思路：1. 子序列不需要连续2. dp[i]代表以nums[i]这个数结尾的最长递增子序列的长度3.'''n = len(nums)if n == 0:return 0dp = [1 for _ in range(n)]for i in range(n):for j in range(i):if nums[i] > nums[j]:dp[i] = max(dp[i], dp[j] + 1)res = max(dp)print(res)return resdef coinChange(coins, amount):'''给你⼀个整数数组 coins，表示不同⾯额的硬币；以及⼀个整数 amount，表示总⾦额。计算并返回可以凑成总⾦额所需的最少的硬币个数。如果没有任何⼀种硬币组合能组成总⾦额，返回 -1（你可以认为每种硬币的数量是⽆限的）。leetcode: 322. 零钱兑换input:coins = [1, 2, 5], amount = 11output:3思路：1. 自底向上:dp[i]=x，目标金额为i时，至少需要x枚硬币2. 自顶向下:def dp()3.'''dp = [amount + 1 for _ in range(amount + 1)]dp[0] = 0  # 金额为0时，需要0枚硬币for i in range(len(dp)):for coin in coins:if i - coin < 0:# 说明给出的coin数值大，凑不出金额i，子问题无解continuedp[i] = min(dp[i], 1 + dp[i - coin])if dp[amount] == amount + 1:return -1return dp[amount]def fib(n):'''斐波那契数，通常⽤ F(n) 表示，形成的序列称为 斐波那契数列。该数列由 0 和 1 开始，后⾯的每⼀项数字都是前⾯两项数字的和。leetcode:509. 斐波那契数input:2output:1思路：1.2.3.'''dp = [1 for _ in range(n)]if n == 1 or n == 2:return 1for i in range(2, n):dp[i] = dp[i - 1] + dp[i - 2]print(dp[n - 1])return dp[n - 1]def maxEnvelops(envelops):'''给你⼀个⼆维整数数组 envelopes，其中 envelopes[i] = [wi, hi]，表示第 i 个信封的宽度和⾼度。当另⼀个信封的宽度和⾼度都⽐这个信封⼤的时候，这个信封就可以放进另⼀个信封⾥，如同俄罗斯套娃⼀样。请计算 最多能有多少个信封能组成⼀组“俄罗斯套娃”信封（即可以把⼀个信封放到另⼀个信封⾥⾯）。leetcode:354. 俄罗斯套娃信封问题input:[[5,4],[6,4],[6,7],[2,3]]output:3思路：1.2.3.'''n_env = len(envelops)sorted_envelops = sorted(envelops, key=lambda x: (x[0], -x[1]))def lenOfLIS(nums):n = len(nums)if n == 0:return 0dp = [1 for _ in range(n)]for i in range(n):for j in range(i):if nums[i] > nums[j]:dp[i] = max(dp[i], dp[j] + 1)print('max LIS: ', max(dp))return max(dp)height = [sorted_envelops[i][1] for i in range(n_env)]print(height)return lenOfLIS(height)if __name__ == "__main__":# jump([2, 3, 1, 1, 4])# print(canJump([2, 3, 1, 1, 4]))# print(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))# rob([1, 2, 3, 1])# rob([2, 7, 9, 3, 1])# print(rob2([2, 3, 2]))# from code_brush.base_problem.binary_tree.binary_tree import buildTreeByArray## t = buildTreeByArray([3, 2, 3, '#', 3, '#', 1])# rob3(t)## lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])print(coinChange([1, 2, 5], 11))fib(6)  # 8maxEnvelops([[5, 4], [6, 4], [6, 7], [2, 3]])