更新中。。。。
动态规划（Dynamic Programming）四要点：
- 递推
- 状态的定义：
- 状态转移方程：
- 最优子结构
70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
class Solution:
def climbStairs(self, n: int) -> int:
# 动态规划
# DP状态的定义：f(n)表示到第n阶的总走法个数
# DP状态转移方程：f(n) = f(n-1) + f(n-2)表示走一阶或走二阶上楼梯
# 斐波那契数列求和
x, y = 1, 1
for _ in range(1,n):
x, y = y, x + y
return y
内存消耗为O(1)，时间复杂度为O(N)。
执行用时 : 48 ms, 在Climbing Stairs的Python3提交中击败了80.81% 的用户
内存消耗 : 13.2 MB, 在Climbing Stairs的Python3提交中击败了35.74% 的用户
斐波那契数列的最优时间复杂度为O(logN)。所以上面的代码还可以再优化。
120. 三角形最小路径和
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
说明：
如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
"""
三角型二维数组：m*n
DP状态定义：dp[i, j]指从下面一层走到当前层，路径和的最小值
DP状态方程：dp[i, j] = min(dp(i+1, j), dp(i+1, j+1)) + triangle[i, j]
DP初始状态: dp[m-1, j] = Triangle[m-1, j]
注意这里比较的不是数组元素值，而是路径和
最后一直递推到dp[0, 0]就是我们要的值了
"""
if not triangle:
return 0
# res指三角形最下面的一层，既是triangle数组里的元素，又是当前的最小路径
res = triangle[-1]
# 状态转移是从倒数第二行开始的（也就是递推的顺序）
for i in range(len(triangle)-2, -1, -1):
for j in range(len(triangle[i])):
res[j] = min(res[j], res[j+1]) + triangle[i][j]
# 上面这一行代码用到了状态压缩的思路，其实就是数组复用而已，因为数组元素用过一次后就用不着了，接着被状态值覆盖掉，这一可以省去不少空间。
return res[0]
执行用时 : 68 ms, 在Triangle的Python3提交中击败了49.63% 的用户
内存消耗 : 13.3 MB, 在Triangle的Python3提交中击败了100.00% 的用户
152. 乘积最大子序列
给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。
示例：
输入: [2, 3, -2, 4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
========================================
输入: [-2, 0, -1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
========================================
输入: [2, 3 , -10, 5, -1]
输出: 300
解释: 负负得正，结果就是全数组的乘积。