- Leetcode303 区域和检索
- Leetcode392 判断子序列
- Leetcode746 最小花费爬楼梯
- Leetcode1025 除数博弈
> 特别鸣谢廖老师教我动态规划，以前对动态规划没有一个很理性的认识。可能这道题会dp都是瞎蒙出来的，换个题 甚至换个条件就无从下手了，现在对简单的DP题至少是头脑比较清晰了，谢谢廖老师 谢谢廖老师！
<h2>以DP解法为主</h2>
下面题目顺序按上面4个来做 ，针对每道题当然有比DP更好的解法，在这里我们主要只讨论DP方法
<h3><a title="题目描述" href="https://leetcode-cn.com/problems/range-sum-query-immutable/">题目描述</a></h3>
<h4></h4>
<pre class="EnlighterJSRAW" data-enlighter-language="null">class NumArray:
def __init__(self, nums: List[int]):
self.dp = [0] * len(nums)
if nums:
self.dp[0] = nums[0]
for i in range(1,len(nums)):
self.dp[i] = self.dp[i-1] + nums[i]
def sumRange(self, i: int, j: int) -> int:
if not self:
return null
return self.dp[j]-self.dp[i-1] if i>0 else self.dp[j]
# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(i,j)
</pre>
#### Note
- 简单的DP题，状态转移方程很好列
- 但其实做题的时候遇到了
1. self.dp来把dp作为全局变量（不知道描述的是不是准确）其实不是一开始就想到的
2. nums非空的边界条件未考虑，空的时候返回null题目未表述清楚 这是题目出得不够好。
<h3><a title="题目描述" href="https://leetcode-cn.com/problems/is-subsequence">题目描述</a></h3>
<h4></h4>
<pre class="EnlighterJSRAW" data-enlighter-language="null"># class Solution:
# def isSubsequence(self, s: str, t: str) -> bool:
# m = len(s)
# n = len(t)
# if not m:
# return True
# if not n:
# return False
# if m==1:
# return s in t
# dp= [[False]*n for i in range(m)]
# for j in range(n):
# dp[0][j] = True
# for i in range(1,m):
# for j in range(1,n):
# if(s[i] == t[j]):
# dp[i][j] = dp[i-1][j-1]
# else:
# dp[i][j] = dp[i][j-1]
# return dp[m-1][n-1]
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
m,n = len(s),len(t)
if not m:
return True
if not n:
return False
for item in s:
temp = t.find(item)
if temp == -1:
return False
t = t[temp+1:]
return True
</pre>
#### Note
- 这道题总体有点像LCS问题，但是用二维数组做DP会超时，降到一维应该没问题。具体降法实现有空再写。。（咕咕咕？）
- 先讲下二维数组DP的方法
1. 首先dp[i][j]表示字符串s、t的前i个、前j个字符组成的串（**记住我们要判断s是否属于t的子序列**），不妨记为si，tj，于是当si为tj子序列时dp[i][j]=True否则为False
2. 那么考虑两种情况，
3. 当s[i]=t[j]时，s中第i个和t中第j个字符显然不对si、tj的从属关系**做贡献了**，也就是说实际上此时s[i]、t[j]可以直接抹去不看， 即dp[i][j]=dp[i-1][j-1]
4. 当s[i]!=t[j]时，t中第j个字符也无法对si是否属于t的子序列做贡献了，于是有dp[i][j]=dp[i][j-1]
5. 最终return dp[m-1][n-1]
- 上面过程可能也有出错的地方OvO
- 方法二是切片法，也是我最终ac的代码，其义自明。
<h3><a title="题目描述" href="https://leetcode-cn.com/problems/min-cost-climbing-stairs/">题目描述</a></h3>
<h4></h4>
<pre class="EnlighterJSRAW" data-enlighter-language="null">class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
dp = cost
n = len(cost)
if(n>2):
for i in range(2,n):
dp[i] = min(dp[i-1],dp[i-2])+cost[i]
return min(dp[n-2],dp[n-1])
else:
return min(dp[0],dp[1])
</pre>
#### Note
- 简单的DP题
<h3><a title="题目描述" href="https://leetcode-cn.com/problems/divisor-game/">题目描述</a></h3>
<h4></h4>
<pre class="EnlighterJSRAW" data-enlighter-language="null">class Solution:
def divisorGame(self, N: int) -> bool:
dp = [False] * (N+1)
if N<=1:
return False
dp[2] = True
for i in range(3, N+1):
for j in range(1,i//2):
if i%j == 0 and dp[i-j]==False:
dp[i] = True
break
return dp[N]
</pre>
#### Note
- 比较tricks的解法是类似之前的Nim游戏，找规律发现偶数必胜否则必输，所以一行return N%2==0即可
- 但我们还是在学习DP解法
- dp[i]表示当前数字为i时，Alice获胜的情况，True表示胜利否则失败，初始化为False
- 不难知道当Alice面对1则输面对2则胜，**且根据游戏规则有dp[i]、dp[i-j]有且只有一个为False**，转移方程大概是形如dp[i]+dp[i-j]=1这样
- 和普通dp不同的只是j需要满足i%j===0而已 题目可解
Leetcode DP简单题4道
