type
status
password
date
slug
summary
category
URL
tags
icon
题型
- 输入序列
A[0,...,n-1]
dp[i]表示为A[0,...,i]的状态。要建立dp[i]与dp[i-1]、dp[i-2]、dp[i-3]、dp[i-4]、...、dp[0]的联系。
LC746. Min Cost Climbing Stairs
数组的每个下标作为一个阶梯，第
i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。示例 1：
题解一
- 状态：到达台阶
i花费的最小体力值
- 边界条件：在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。所以
dp[1]=dp[0]=0
- 状态转移方程：
dp[i]=min{dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]}
自顶向下
自低向上
状态压缩
上述代码的时间复杂度和空间复杂度都是 。注意到当 时， 只和 与 有关，因此可以使用滚动数组的思想，将空间复杂度优化到 。
LC198. House Robber
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
题解一
- 状态：设动态规划列表 ，代表前 个房子在满足条件下的能偷窃到的最高金额。
- 边界条件：在第0个房屋，能够偷窃的最高金额是
dp[0]=H[0]；在第1个房屋，能够偷窃的最高金额是前两个房屋中的最高金额dp[1]=max(H[0],H[1])
- 状态转移方程：
dp[n]=max(dp[n-1],dp[n-2]+H[n])
自顶向下
自低向上
状态压缩
题解二
- 状态：设动态规划列表 ，代表前 个房子在满足条件下的能偷窃到的最高金额。注意第 个房屋必须偷窃。如果第i个元素必须在内，此时使用自低向上的方法更简单。
- 边界条件：在第0个房屋，能够偷窃的最高金额是
dp[0]=H[0]；在第1个房屋，能够偷窃的最高金额是dp[1]=H[1]
- 状态转移方程：
dp[n]=max(dp[n-2])+H[n]
自低向上
LC213. House Robber II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例 1：
题解一
此题是 198. 打家劫舍 的拓展版： 唯一的区别是此题中的房间是环状排列的（即首尾相接），而 198. 题中的房间是单排排列的；而这也是此题的难点。
环状排列意味着第一个房子和最后一个房子中只能选择一个偷窃，如果偷窃了第一间房屋，则不能偷窃最后一间房屋，因此偷窃房屋的范围是第一间房屋到最后第二间房屋；如果偷窃了最后一间房屋，则不能偷窃第一间房屋，因此偷窃房屋的范围是第二间房屋到最后一间房屋。综上可以把此环状排列房间问题约化为两个单排排列房间子问题：
- 在不偷窃第一个房子的情况下（即
nums[1:]），最大金额是 ；
- 在不偷窃最后一个房子的情况下（即
nums[:n-1]），最大金额是 。
综合偷窃最大金额： 为以上两种情况的较大值，即 。
- 状态：在第n 个房屋，能够偷窃的最高金额。
- 边界条件：因为环状排列可以转换为两个单排排列，所以边界条件有两种。
- 在不偷窃第一个房子的情况下：
dp[start]=nums[1]dp[start+1]=max(nums[1],nums[2]) - 偷窃第一个房子：
dp[start]=nums[0]dp[start+1]=max(nums[0],nums[1])
- 状态转移方程：
dp[n]=max(dp[n-1],dp[n-2]+H[n])
自顶向下
自低向上
状态压缩
LC300. LIS
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
题解一
与上面三道题不同的地方是，状态的定义必须包含最后一个元素。也就是包含最后一个元素的情况下的最大子序列。
- 状态： 为考虑前 个元素，以第 个数字结尾的最长上升子序列的长度，注意 必须被选取（与前面两道题不同的地方）。
- 边界条件：因为每个元素都可以单独成为子序列，此时长度都为1。所以 所有元素都置为1。
- 状态转移方程：，考虑每轮计算新 时，遍历 列表区间，做以下判断：综上状态转移方程是
dp[i] = max(dp[i], dp[j] + 1) for j in [0, i)。 - 当 时： 可以接在 之后（此题要求严格递增），此情况下最长上升子序列长度为 ；
- 当 时： 无法接在 之后，此情况上升子序列不成立，跳过。
自低向上
Game of 5 power
给定一个只包含
0 和 1 的字符串 s 。将字符串 s 分为 k 段，使得每一个子串是 5 的幂。如果不能将字符串进行分割，则返回-1。S=“101101101” return 3 （101=5、101=5、101=5）S=“1111101” return 1 （1111101=125）S=“0000” return -1S=“100” return -1
- 状态转移方程：对于字符串
str[0:i]，遍历j in range(0,i+1)，如果dp[j]!=-1且str[j+1:i+1] is power of 5，那么此时可分，此时可以分为dp[i]+1个子串。选取所有可分case得最小值。
设
dp[i]为字符串str[0,i]最少分割成dp[i]个子串题解一
- 状态：设
dp[i]为字符串str[0,i]最少分割成dp[i]个子串，使得每个子串是power of 5
- 边界条件：设置原始
dp[i]=-1。使得初始时都不可分
- 状态转移方程：对于字符串
str[0:i]，遍历j in range(0,i+1)，如果dp[j]!=-1且str[j+1:i+1] is power of 5，那么此时可分，此时可以分为dp[i]+1个子串。选取所有可分case得最小值。