动态规划

题目：

Maximum Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

题目是说，给你一串数，有正有负 要求出最大的连续子串。

其实就是标准的动态规划问题：
随着遍历这个数组，在到每一个位置的时候，弄一个局部最大L值，代表以当前位置为结尾的最大子串，比如说我遍历到第i个，那么以第i个为结尾的最大子串就是我们要求的L。

比如这个题目：
-2 , 1, −3,4,−1,2,1,−5,4
位置0，L=x=-2，没得选
位置1，要以x=1为结尾的最大的，那肯定不要带上之前的-2,只要1就好L=x=1
位置2，因为本身x=-3，加上上一个位置L 是正数1，所以L=L+x=-3+1=-2。
下面以此类推得到：

对应的L应该是：
-2, 1, -2,4,3,5,6,-1,3

而全局最大值G就是我们最终想要的结果，
肯定这个全局最大值出自局部最大值。
（因为全局最大的那个子串的结尾肯定在数组里，言外之意就是不管怎么样这个G都肯定出自L）
最后找到最大的那个L就是我们想要的G了。

classSolution(object):defmaxSubArray(self, nums):

l = g = -1000000000forninnums:
            l = max(n,l+n)
            g = max(l,g)returng

2.给定一个数列，长度为N，
求这个数列的最长上升（递增）子数列（LIS）的长度.
以
1 7 2 8 3 4
为例。
这个数列的最长递增子数列是 1 2 3 4，长度为4；
次长的长度为3， 包括 1 7 8; 1 2 3 等.

所以我们来重新定义这个问题：
给定一个数列，长度为N，
设为：以数列中第k项结尾的最长递增子序列的长度.
求中的最大值.
https://www.zhihu.com/question/23995189/answer/35429905
def maxascendingListNum(num):
f1=1
for i in range(0,len(num):
if num[k]>num[i] and k>i>=0:
Fk=max(Fi+1)
G=max(g,Fk)
return G

121. Best Time to Buy and Sell Stock
http://blog.csdn.net/u014251967/article/details/52517256
def maxprofit(nums):
g=-1000
for i in range(1,len(nums)):
Nmin=min(nums[:i])/Nmin=nums(0),Nmin=min(Nmin,nums(i))
F=nums(i)-Nmin
G=max(G,F)
return G

LeetCode 64. Minimum Path Sum
http://www.cnblogs.com/fangdai/archive/2017/05/15/6858786.html
http://www.jianshu.com/p/cad4ae5f08fb
class Solution(object):
　　def minPathSum(self, grid):
　　　　"""
　　　　:type grid: List[List[int]]
　　　　:rtype: int
　　　　"""
　　　　m = len(grid)
　　　　n = len(grid[0])
　　　　grid1 = [[0 for i in range(n)] for j in range(m)]
　　　　grid1[0][0] = grid[0][0]
　　　　for i in range(0, m):
　　　　　　for j in range(0, n):
　　　　　　　　if i != 0 and j == 0:
　　　　　　　　　　grid1[i][j] = grid1[i - 1][j] + grid[i][j]
　　　　　　　　elif i == 0 and j != 0:
　　　　　　　　　　grid1[i][j] = grid1[i][j - 1] + grid[i][j]
　　　　　　　　elif i != 0 and j != 0:
　　　　　　　　　　grid1[i][j] = min(grid1[i - 1][j],grid1[i][j - 1]) + grid[i][j]
　　　　return grid1[m - 1][n - 1]


303. Range Sum Query - Immutable
http://www.jianshu.com/p/03ce80f5d953
classNumArray(object):
def__init__(self, nums):"""
        :type nums: List[int]
        """self.dp = numsforiinrange(1, len(nums)):
            self.dp[i] += self.dp[i -1]defsumRange(self, i, j):"""
        :type i: int
        :type j: int
        :rtype: int
        """returnself.dp[j] - (self.dp[i -1]ifi >0else0)



70. Climbing Stairs
https://leetcode.com/problems/climbing-stairs/discuss/# Top down - TLE
ht       https://leetcode.com/problems/climbing-stairs/discuss/
def climbStairs1(self, n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    return self.climbStairs(n-1)+self.climbStairs(n-2)
 
# Bottom up, O(n) space
def climbStairs2(self, n):
    if n == 1:
        return 1
    res = [0 for i in xrange(n)]
    res[0], res[1] = 1, 2
    for i in xrange(2, n):
        res[i] = res[i-1] + res[i-2]
    return res[-1]

# Bottom up, constant space
def climbStairs3(self, n):
    if n == 1:
        return 1
    a, b = 1, 2
    for i in xrange(2, n):
        tmp = b
        b = a+b
        a = tmp
    return b


6
7
8
9
10