主要思想：
1、寻找重叠子问题，然后列出状态转移方程
2、通过自顶向下的备忘录或者自底向上的dp table来优化
凑零钱问题
k中面值的硬币，面值分别为[1,2,5]，每种硬币的数量无限，再给一个总金额amount。求出最少需要几枚硬币凑出这个金额。如果不能凑出，返回-1。
状态转移方程：
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
res = {}
res[0] = 0
for i in range(1 , amount+1):
res[i] = float('INF') # 这里要先设置为无穷大，这样就会求出最小值
for coin in coins :
if i >= coin :
res[i] = min(res[i-coin] + 1 , res[i])
if res[amount]!= float('INF'):
return res[amount]
else:
return -1
以上代码采用自底向上的方式来消除重叠子问题。
完全平方数
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
class Solution:
def numSquares(self, n: int) -> int:
max_num = math.floor(math.sqrt(n))
nums = [i ** 2 for i in range(1 , max_num +1)]
# 转变成换零钱问题
res = {}
res[0] = 0
for i in range(1, n+1):
res[i] = float('INF')
for num in nums :
if i - num >= 0:
res[i] = min(res[i] , res[i-num] + 1)
if res[i] != float('INF'):
return res[n]
乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
动态规划题
class Solution:
def maxProduct(self, nums: List[int]) -> int:
length = len(nums)
if length == 1:
return nums[0]
dpmax = {}
dpmin = {}
dpmax[0] = nums[0]
dpmin[0] = nums[0]
# 把问题转化为求以nums[i]结尾，最大乘积子数组
for i in range(1,length) :
dpmax[i] = max(nums[i] , dpmax[i-1] * nums[i] , dpmin[i-1] * nums[i])
dpmin[i] = min(nums[i] , dpmax[i-1] * nums[i] , dpmin[i-1] * nums[i])
ans = dpmax[0]
for i in range(1,len(dpmax)):
ans = max(ans,dpmax[i])
return ans
最大子序列和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
思路：
定义状态（子问题）：dp[i]表示以nums[i]为结尾的连续子数组的最大和。注意这里是结尾！也就是一定会包含nums[i]这个数在子序列中。
动态转移方程（描述子问题之间的联系）即为：
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
size = len(nums)
if size == 0:
return 0
dp = [0 for _ in range(size)]
dp[0] = nums[0]
for i in range(1, size):
if dp[i - 1] >= 0:
dp[i] = dp[i - 1] + nums[i]
else:
dp[i] = nums[i]
return max(dp)
补充一个对解决动态规划问题非常重要的一个概念：“无后效性”
为了保证计算子问题能够按照顺序、不重复地进行，动态规划要求已经求解的子问题不受后续阶段的影响。这个条件也被叫做「无后效性」。换言之，动态规划对状态空间的遍历构成一张有向无环图，遍历就是该有向无环图的一个拓扑序。有向无环图中的节点对应问题中的「状态」，图中的边则对应状态之间的「转移」，转移的选取就是动态规划中的「决策」。
落实在实际解决问题时：
- 在定义子问题时，不能选择那种结果里包含不确定信息的子问题，如果选择这样的子问题定义方法，会导致后面的阶段求解的子问题无法得到。
- 解决后效性的方法有两种（代码层面）：
- 状态数组增加维度，例如：股票系列问题
- 把状态定义的更细致、更准确。
打家劫舍问题
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 。
解题思路：
- 状态：面前每一户人家的index，选择：偷这一家还是不偷这一家
- 两个选择中，选取最大的值即为当前状态的最大money
- 子问题的定义：
dp[i]：前i个房子在满足条件下能偷窃到的最高金额 - 状态转移方程：
对于前n-1个房子来说，最大金额为dp[i-1]，那么对于第n个房子，有两种选择：
- 抢第n个房子，那么第n-1个房子不能抢，那么此时最大金额就是
dp[n-2] + nums[n] - 不抢第n个房子，那么第n-1个房子就是可以抢劫的，那么此时最大金额就是
dp[n-1]
那么对于dp[n]= max(dp[n-2]+nums[n],dp[n-1])
- base 情况：
dp[0] = 0，dp[1]=nums[0] - 返回结果：dp最后一个元素值
class Solution:
def rob(self, nums: List[int]) -> int:
dp={}
n = len(nums)
dp[0] = nums[0]
dp[-1] = 0
for i in range(1,n):
dp[i] = max(dp[i-1] , nums[i] + dp[i-2])
return dp[n-1]
以上解决办法为自底向上的方法，下面贴出用递归自顶向下的方式，并用备忘录进行剪枝，从而解决运行时间。
class Solution:
def rob(self, nums: List[int]) -> int:
length = len(nums)
memo = {}
memo[-1] = 0
memo[0] = nums[0]
def helper(end): # 求前end个房子，抢劫到的最大金额
if end in memo:
return memo[end]
not_do = helper(end-1)
do = helper(end-2)+nums[end]
res = max(do,not_do)
memo[end] = res
return res
return helper(length-1)
leetcode213. 打家劫舍2
房屋并不是线性的数组了，而是围成一个圈，也就是如果抢劫了最后一户人家，那么就不能抢第一户人家；如果抢劫了第一户人家，那么就不能抢劫第二户人家。
class Solution:
def rob(self, nums: List[int]) -> int:
dp1={}
n = len(nums)
if n == 1: return nums[0]
# 不偷第一家
dp1[0] = 0
dp1[-1] = 0
for i in range(1,n):
dp1[i] = max(dp1[i-1],nums[i] + dp1[i-2])
# 不偷最后一家
dp2={}
dp2[0],dp2[-1] = nums[0],0
for i in range(1,n-1):
dp2[i] = max(dp2[i-1],nums[i] + dp2[i-2])
return max(dp1[n-1],dp2[n-2])
以上两种情况的区别在于：不偷第一家的话，dp[0]=0, 而如果偷的话dp[0] = nums[0]
leetcode337. 打家劫舍3
这里房屋如何布置又变化了一下，变成是二叉树的分布。二叉树的遍历只能从root开始，才能到叶子节点。不能直接通过index获取元素。所以这里只能采用递归的方式，自顶向下的解决该问题。
示例 1:
输入: [3,2,3,null,3,null,1]
3
/ \
2 3
\ \
3 1
输出: 7
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
class Solution:
def rob(self, root: TreeNode) -> int:
memo = {}
def helper(root):
if root== None: return 0
if root in memo: return memo[root]
do_it = root.val
if root.left:
do_it += helper(root.left.left) + helper(root.left.right)
if root.right:
do_it += helper(root.right.left) + helper(root.right.right)
not_do_it = helper(root.left) + helper(root.right)
res = max(do_it,not_do_it)
memo[root] = res
return res
helper(root)
return memo[root]
62. 不同路径1
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[0] * n for _ in range(m)]
dp[0][0] = 1
for i in range(0, m):
for j in range(0, n):
if i == 0 and j == 0: continue
if i == 0:
dp[i][j] = dp[i][j - 1]
elif j == 0:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[m-1][n-1]
这题注意1）临界点的特殊处理 2）还有dp数组在创建的时候要用列表推导式，涉及到python中的浅拷贝和深拷贝问题
63.不同路径2
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
m = len(obstacleGrid)
n = len(obstacleGrid[0])
dp = [[0] * n for _ in range(m)]
dp[0][0] = 0 if obstacleGrid[0][0] == 1 else 1 # 这里注意初始值要相对于前面的代码需要修改
for i in range(0, m):
for j in range(0, n):
if obstacleGrid[i][j] == 1: continue
if i == 0 and j == 0: continue
if i == 0:
if obstacleGrid[i][j-1] == 1:
dp[i][j] = 0
else:
dp[i][j] = dp[i][j - 1]
elif j == 0:
if obstacleGrid[i-1][j] == 1:
dp[i][j] = 0
else:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[m-1][n-1]
这里有个微妙的地方：写完代码之后我在思考为什么if obstacleGrid[i][j] == 1: continue没有对dp[i][j]赋值为0也能提交正确，后来想到我初始化dp数组的时候，所有路径的值全部初始化的是0，所以这里不将dp[i][j]置为0也是正确的。
最小路径和
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
这一题我一开始的想法是图搜索算法，也就是广度优先搜索，但后来看了下笔记，发现这道题目和广度优先搜素算法不一样的地方在于：广度优先算法不能处理图中带有权重的图搜索问题，如果想要处理无环有权重的图搜索问题，要用Dijkstra算法。
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
dp = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
if i == 0 and j == 0:
dp[i][j] = grid[0][0]
elif i==0:
dp[i][j] = dp[i][j-1] + grid[i][j]
elif j==0:
dp[i][j] = dp[i-1][j] + grid[i][j]
else:
dp[i][j] = min(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j])
return dp[m-1][n-1]
