Dynamic Programming
303. 区域和检索 - 数组不可变
题目描述:
给定一个整数数组 nums,求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和,包含 i, j 两点。
示例:
给定 nums = [-2, 0, 3, -5, 2, -1],求和函数为 sumRange()
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
说明:
你可以假设数组不可变。
会多次调用 sumRange 方法。
解答
起初不太明白为什么这个题目是动态规划问。后来想到,如果每次求一个区间都要重新计算的话,复杂度比较高,可能存在很多重复计算。
如果求得 0-j 的和,每次计算只需要用 0-j 的和减去 0-i 的和,因为区间是闭区间,因此还要加上 i 的值。
先写了一个每次都重新计算的——超时了
考虑用空间替换时间,写一个数组保存 0-每一个数
的值
1 | class NumArray(object): |
392. 判断子序列
给定字符串 s 和 t ,判断 s 是否为 t 的子序列。
你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长(长度 ~= 500,000),而 s 是个短字符串(长度 <=100)。
字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"
是"abcde"
的一个子序列,而"aec"
不是)。
示例 1:
s = "abc"
, t = "ahbgdc"
返回 true
.
示例 2:
s = "axc"
, t = "ahbgdc"
返回 false
.
1 | class Solution(object): |
746. 使用最小花费爬楼梯
题目描述:
数组的每个索引做为一个阶梯,第 i个阶梯对应着一个非负数的体力花费值 cost[i]
(索引从0开始)。
每当你爬上一个阶梯你都要花费对应的体力花费值,然后你可以选择继续爬一个阶梯或者爬两个阶梯。
您需要找到达到楼层顶部的最低花费。在开始时,你可以选择从索引为 0 或 1 的元素作为初始阶梯。
示例 1:
1 | 输入: cost = [10, 15, 20] |
示例 2:
1 | 输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] |
题解:
刚开始没有太看懂这道题是什么意思,看了评论区大家的解释,
大体可以理解为你可以一次走一步或者两步楼梯,但是到了这个楼梯,在该楼梯上的花费必须要有。
求最小的爬楼梯花费,有点像之前的爬楼梯的题目。
因此对于当前台阶i,你可以从前一级过来,也可以从前一级的前一级过来,
由于你到达了该台阶,总花费需要加上当前第i台阶的花费
代码:
1 | class Solution(object): |
- 本文作者: Kelly Liu
- 本文链接: http://tiantianliu2018.github.io/2019/09/30/leetcode-Dynamic-Programming/
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!