动态规划问题总结
1.求连续子数组的最大求和以及乘积问题
动态规划问题最核心是需要找到动态性，即当前的Dp[i]和Dp[i-1]之间的关系，然后不断更新Dp。而Dp之间的动态转换根据不同的题目有不同的转换，需要通过一定的思维训练，或者说是解题的直觉和敏锐性。
（1）最大子数组的和:
Dp[i]则表示到数组下标i的最大数组值，其求解需要依赖于到前一个数组下标的最大值，若Dp[i-1]<0则此时的Dp[i]=nums[i],否则Dp[i]=Dp[i-1]+nums[i]总结起来就是Dp[i]=max(Dp[i-1]+nums[i],nums[i])
（2）最大子数组的乘积:
最大子数组的乘积和最大子数组的和非常相似但又不同，和的话，遇到0或者负数，求和不变或者减小，而变为乘法时，当前的最大乘积可能变成最小乘积，所以需要维护两个Dp数组，一个用来表示包含nums[i]的子数组的最大乘积，一个表示包含nums[i]的子数组的最小乘积(接下来的要乘的数是负数的情况)。
当然，也可以分情况讨论当前的nums[i]的正负数，比较两个数而非三个数节省时间效率。
注意点：有时候并不一定是一个Dp数组，可能是多个Dp数组
2.最长递增子序列问题
阿里巴巴20年暑假实习生笔试题中出现的最长旋律问题：
小明在学旋律，每段旋律都可以用字符串来表示，并且旋律的每个字符的ASCALL码递增的。比如以下4段旋律 :
aaa
bcd
bcdef
zzz
现在就是要求，小明能够把这些旋律拼接起来组成最长的旋律。
比如上述例子输出 11， 最长的旋律为 aaabcdefzzz。
这道题目和Leetcode的Word break非常相似，首先需要将每段旋律按照最后一个字母从小到大排列，最后一个字母相同时，按照第一个字母从大到小排列，然后维护一个和字符串的个数相同大小的数组dp,dp[i]表示到第i个字符时能组成的最长的旋律，伪代码如下：
#因为每段旋律都是递增的，最后一个字符相同时，按照第一个字符由大到小排列，即为旋律字符串的长度由小到大的排列顺序
dp=[0]*len(num)
dp[0]=len(num[0])
for i in range(len(num)):
for j in range(i):
if num[j][-1]<num[i][0]:
dp[i]=max(dp[i]+len(num[j],len(nums[i]))
return dp[len(num)-1]
同样地，word break问题也非常相似：
Description:
Leetcode139:https://leetcode.com/problems/word-break/
题目大意是给定一个字符串，和一个字符字典，判断字符串能否由字符字典中的字符构成，同样需要维护一个dp数组，表示到字符下标[i]结束的字符能否由字符字典构成，需要两层循环，第二层循环从起始遍历到i位置的时候判断子字符串是否在字典中，两个问题都需要再往前看一次，具体代码如下：
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: bool
"""
dp=[False for t in range(len(s)+1)]
dp[0]=True
for i in range(len(s)+1):
for j in range(i):
print(i,j,s[j:i])
if dp[j] and (s[j:i] in wordDict):
print(i)
dp[i]=True
break
print(dp)
return dp[len(s)]
求解动态规划问题，最重要的是要找到动态转移方程，在求解问题的时候先写出伪代码，然后再写代码会更加简洁高效。
