Failure

LeetCode Challenge 🏆
> 挑战目标🎖: 100道DP题
   时间    🗓:  25⁄70 （2018-09-13 👉🏻 2018-11-15）
   进度    🛴:  41⁄100
成功奖励🍭: ██████████

Solved: 🥈🥈🥈🥈🥉 Log:
18-09-28: 取消每次记录天吧，只记录每周刷了多少道题，感觉时间分配不足了。
18-09-30: 决定50道题之后开个part2的记录，不然篇幅太长了，虽然已经很长了。 18-10-01～18-12-17: Pause

Week4:

Solved 7 problems

309-M

309. Best Time to Buy and Sell Stock with Cooldown
Difficulty: ★★★★☆
Beats: %
Time Complexity: O($n$)

Code:

def maxProfit(self, prices):
    if len(prices) < 2: return 0
    sell, buy, prev_sell, prev_buy = 0, -prices[0], 0, 0
    for price in prices:
        prev_buy = buy
        buy = max(prev_sell - price, prev_buy)
        prev_sell = sell
        sell = max(prev_buy + price, prev_sell)
    return sell

764-M

764. Largest Plus Sign
Difficulty: ★★★☆☆
Beats: 22.64%
Time Complexity: O($n^2$)

Code:

def orderOfLargestPlusSign(self, N, mines):
    matrix = [[1]*N for _ in range(N)]
    dp = [[0] * (N+2) for _ in range(N+2)]
    up = [[0] * (N+2) for _ in range(N+2)]
    down = [[0] * (N+2) for _ in range(N+2)]
    left = [[0] * (N+2) for _ in range(N+2)]
    right = [[0] * (N+2) for _ in range(N+2)]
    for i in range(1, N+1):
        for j in range(1, N+1):
            dp[i][j] = 1
    for mine in mines:
        x, y = mine
        matrix[x][y] = 0
        dp[x+1][y+1] = 0

    for i in range(1, N+1):
        for j in range(1, N+1):
            if matrix[i-1][j-1]:
                up[i][j] = up[i-1][j] + matrix[i-1][j-1]
                left[i][j] = left[i][j-1] + matrix[i-1][j-1]
            if matrix[i-1][N-j]:
                right[i][N+1-j] = right[i][N+2-j] + matrix[i-1][N-j]
            if matrix[N-i][j-1]:
                down[N+1-i][j] = down[N+2-i][j] + matrix[N-i][j-1]
    res = 0
    for row in range(1, N+1):
        for col in range(1, N+1):
            if matrix[row-1][col-1] == 0:
                dp[row][col] = 0
            else:
                dp[row][col] = min(up[row-1][col], down[row+1][col], left[row][col-1], right[row][col+1]) + 1
            res = max(res, dp[row][col])
    return res

740-M

740. Delete and Earn
Difficulty: ★★★☆☆
Beats: 40.95%
Time Complexity: O($n$)

Code:

def deleteAndEarn(self, nums):
    if not nums: return 0
    counter = collections.defaultdict(int)
    vis = collections.defaultdict(int)
    for num in nums:
        counter[num] += 1
        vis[num] = 1
    nums = sorted(list(set(nums)))
    if len(nums) == 1: return nums[0]*counter[nums[0]]

    dp = [0]*len(nums)

    dp[0] = counter[nums[0]]*nums[0]
    if nums[1] - 1 != nums[0]:
        dp[1] = dp[0] + counter[nums[1]]*nums[1]
    else:
        dp[1] = max(dp[0], counter[nums[1]]*nums[1])
    for i in range(2, len(nums)):
        cur = nums[i]*counter[nums[i]]
        if nums[i]-1 != nums[i-1]:
            dp[i] = dp[i-1] + cur
        else:
            dp[i] = max(dp[i-1], dp[i-2] + cur)
    return max(dp)

377-M

377. Combination Sum IV Difficulty: ★★★☆☆
Beats: 16.16%
Time Complexity: O($n^2$)

Code:

def combinationSum4(self, nums, target):
    nums = sorted([num for num in nums if num <= target])
    if not nums: return 0
    res = [0] * (target+1)
    res[0] = 1
    for i in range(nums[0], target+1, 1):
        smaller = list(num for num in nums if num <= i)
        for num in smaller:
            res[i] += res[i-num]
    return res[-1]

962-M

962. Maximum Width Ramp
Difficulty: ★★★☆☆

def maxWidthRamp(self, A):
    n = len(A)
    res = [0] * n
    for i in range(1, n):
        # if A[i] >= A[i-1] and res[i-1] != 0:
        #     res[i] = res[i-1] + 1
        # else:
        for j in range(0, i):
            if A[i] >= A[j]:
                res[i] = i - j
                break
    return max(res)

486-M

486. Predict the Winner
Difficulty: ★★★★★
Explanation: Solution
Remark: 有的时候就会陷入某一步定住，不知道怎么继续下去。想到分别计算Player1和Player2的最大和关系，sum1 > sum2，却想不到深层或者说再底层的关系，怎么解？(其实还是要回归到DP问题，分析最优子结构、状态、状态转移)

Approach #4:
最优子结构性质：
我们可以观察到，给定子数组nums[x:y]，对当前玩家而言的有效得分只依赖nums整个数组中[x,y]范围内的元素。
就看当前玩家本轮取的是nums[x]还是nums[y]，以及取完后另一个玩家用剩余元素可能达到的最高分数。
因此，当前有效得分不受[x,y]之外的元素影响。

假设我们已知nums[x+1: y] 和 nums[x:y-1]的最大有效得分情况，那么我们就可以轻松得到nums[x:y]的有效的最高得分情况 max(nums[x] - score[x+1][y], nums[y] - score[x][y-1]。

因此得到状态方程:
dp[i, j] = nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]。

931-M

931. Minimum Falling Path Sum
Difficulty: ★★★☆☆
Beats: 45.24%
Time Complexity: O($n^2$) Remark: 最小问题，容易发现状态方程，需要注意边界条件的处理。

Explanation:
这里定义状态为从顶层落到第i层，第j个元素位置处的最小和。
那么对于第i+1层非边界元素位置，其最小值取决于上一层的相邻三个元素i-1,i,i+1的最小值；边界元素只考虑两个相邻元素。
容易得到我们的状态方程： res[i+1][j] = A[i+1][j] + min(res[i][j-1], res[i][j], res[i][j+1])。
Code:

def minFallingPathSum(self, A):
    if not A:
        return 0
    if len(A) == 1:
        return min(A[-1])
    size = len(A)
    res = [[0]*size for i in range(size)]
    res[0] = A[0]
    for row in range(1, size):
        for col in range(size):
            if col == 0:
                res[row][col] = A[row][col] + min(res[row-1][col], res[row-1][col+1])
            elif col == size - 1:
                res[row][col] = A[row][col] + min(res[row-1][col-1], res[row-1][col])
            else:
                res[row][col] = A[row][col] + min(res[row-1][col-1], res[row-1][col], res[row-1][col+1])
    return min(res[-1])

Week3:

Solved 8 problems

139-M

139. Word Break
Difficulty：★★★☆☆
Beats: 81%
Time Complexity: O(nwd)
Remark: 思路清晰，DP.

Explanation:

The idea is the following:

d is an array that contains booleans

d[i] is True if there is a word in the dictionary that ends at ith index of s AND d is also True at the beginning of the word

Example:

s = “leetcode”

words = [“leet”, “code”]

d[3] is True because there is “leet” in the dictionary that ends at 3rd index of “leetcode”

d[7] is True because there is “code” in the dictionary that ends at the 7th index of “leetcode” AND d[3] is True

The result is the last index of d.

Code:

def wordBreak(self, s, wordDict):
    n = len(s)
    dp = [False] * n
    for i in range(n):
        for word in wordDict:
            if word == s[i-len(word)+1 : i+1] and (dp[i-len(word)] or i - len(word) == -1):
                dp[i] = True
                break
    return dp[-1]

464-M

464. Can I Win
>Difficulty：★★★★★
Beats: 76%
Time Complexity: O(n^2)
Remark: 博弈论，以及移位操作表示数字是否用过的状态。不会。

liuchou的博客

Code:

def canIWin(self, M, T):
    def win(M, T, m, state):
        if T <= 0: return False
        if m[state] != 0: return m[state] == 1
        for i in range(M):
        if (state & (1 << i)) > 0: continue
        if not win(M, T - i - 1, m, state | (1 << i)):
            m[state] = 1
            return True
        m[state] = -1
        return False

    s = M * (M + 1) / 2
    if s < T: return False
    if T <= 0: return True
    if s == T: return (M % 2) == 1

    m = [0] * (1 << M)
    return win(M, T, m, 0)

650-M

650. 2 Keys Keyboard
>Difficulty：★★★☆☆
Beats: 100%
Time Complexity: O(n)
Remark: 多尝试几个n，就会发现其中蕴含的规律。

Explanation:
什么时候复制、粘贴？
当剩余元素数目是当前已有元素数目的整数倍的时候，如果已复制长度小于已有元素数目，更新复制长度，操作+1，接着复制，反复这个过程，直至剩余元素为0。

def minSteps(self, n):
    res, cpl, ops = 2, 1, 2
    if n == 1: return 0
    if n == 2: return 2
    rawn = n
    n = n - res
    while n>0:
        if n % res == 0:
            # do copy
            if cpl < res:
                cpl = res
                ops += 1
        # do paste
        res += cpl
        n -= cpl
        ops += 1
    return ops

838-M

838. Push Dominoes
>Difficulty：★★★★☆
Beats: 84.30%
Time Complexity: O(n)
Remark: 理解几种普遍的倒下的情况，O(n)可以做。

Intuition: Whether be pushed or not, depend on the shortest distance to ‘L’ and ‘R’.
Also the direction matters.

Here is another idea that focus on ‘L’ and ‘R’.
‘R……R’ => ‘RRRRRRRR’
‘R……L’ => ‘RRRRLLLL’ or ‘RRRR.LLLL’
‘L……R’ => ‘L……R’
‘L……L’ => ‘LLLLLLLL’

Code:

def pushDominoes(self, d):
    d = 'L' + d + 'R'
    res = []
    i = 0
    for j in range(1, len(d)):
        if d[j] == '.': continue
        middle = j - i - 1
        if i: res.append(d[i])
        if d[i] == d[j]: res.append(d[i] * middle)
        elif d[i] == 'L' and d[j] == 'R': res.append('.' * middle)
        else: res.append('R' * (middle / 2) + '.' * (middle % 2) + 'L' * (middle / 2))
        i = j
    return ''.join(res)

646-M

646. Maximum Length of Pair Chain
>Difficulty：★★★☆☆
Beats: 40.26%
Time Complexity: O(n^2)
Remark: 经常性拿到这种二元变量的题有些没思路，学会使用python的lambda；思路还是比较清晰的，用DP的一般步骤套，可以想到怎么做。

Explanation:
首先判断是DP问题：要求最长的chain，符合重复子问题、最优子结构的性质。

其次，它的状态，可以定义为到第i个元素时，以它结尾的和它前面的元素能组成的最长链。

状态转移，如果pairs[i]能放在pairs[i-1]后面，那么它最长就是在前者基础上加1。
如果不能，我们就需要找到那个能放的，因此需要遍历0...i-2个元素，找到即可。

Code:

def findLongestChain(self, pairs):
    pairs.sort(key=lambda r:r[0])
    n = len(pairs)
    dp = [0]*n
    dp[0] = 1
    if pairs[1][0] > pairs[0][1]:
        dp[1] = dp[0] + 1
    else:
        dp[1] = 1
    for i in range(2, n):
        if pairs[i][0] > pairs[i-1][1]:
            dp[i] = dp[i-1] + 1
        else:
            j = i - 2
            while j > -1:
                if pairs[j][1] < pairs[i][0]:
                    break
                j -= 1
            dp[i] = dp[j] + 1
    return dp[-1]

221-M

221. Maximal Square
>Difficulty：★★★☆☆
Beats: 67.54%
Time Complexity: O(nm)
Remark: 多举几个例子就能发现背后的状态方程了，不算难。

Explanation:
假定状态是以s[i][j]作为右下角的符合条件的正方形的边长dp[i][j]，那么它由周围哪几个状态决定呢？
>[[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]] [[“1”,“0”],[“0”,“0”]] [[“1”,“0”,“1”,“0”],[“1”,“0”,“1”,“1”],[“1”,“0”,“1”,“1”],[“1”,“1”,“1”,“1”]] [[“0”,“0”,“0”,“1”],[“1”,“1”,“0”,“1”],[“1”,“1”,“1”,“1”],[“0”,“1”,“1”,“1”],[“0”,“1”,“1”,“1”]]

给出上面4个例子，其结果是4，1，4，9。自己尝试推导一下。

Code:

def maximalSquare(self, matrix):
    if not matrix: return 0
    n = len(matrix)
    m = len(matrix[0])
    dp = [[0] * (m+1) for _ in range(n+1)]
    res = 0
    for i in range(1, n+1):
        for j in range(1, m+1):
            if matrix[i-1][j-1] == "1":
                dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                res = max(res, dp[i][j])
    return res*res

091-M

91. Decode Ways
>Difficulty：★★☆☆☆
Beats: 100%
Time Complexity: O(n)
Remark: 注意对‘0’进行特殊处理，简单DP。

Code:

def numDecodings(self, s):
    d = [0]*(len(s)+1)
    d[0] = 1

    for i in range(1,len(d)):
        if s[i-1] != '0':
            d[i] += d[i-1]
        if (i > 1) and ('09' < s[i-2:i] < '27'):
            d[i] += d[i-2]              
    return d[-1]

152-M

152. Maximum Product Subarray
>Difficulty：★★★☆☆
Beats: 47.25%
Time Complexity: O(n)
Remark: 写了一段程序只有最后一个样例过不了，很长的一个数组，15000，超内存应该是其次，最主要还是算法不够好，而且优化的方向就在内存上，为什么会需要n^2的内存。以及，之前的最大和最小在当前数为负数时的转化，题目的思考还是不够深入。

Code:

def maxProduct(self, nums):
    n = len(nums)
    res = nums[0]
    rx, rm = nums[0], nums[0]
    for i in range(1, n):
        if nums[i] < 0:
            tmp = rx
            rx = rm
            rm = tmp
        rx = max(nums[i], nums[i]*rx)
        rm = min(nums[i], nums[i]*rm)
        res = max(res, rx)
    return res

Week2

中秋放假，就这么混吗？路那么长，多停一天，可能就走不完了。 Solved 8 problems.

Day14

Date: 18-09-26

718-M

718. Maximum Length of Repeated Subarray
>Difficulty：★★★☆☆
Beats: 63.52%
Time Complexity: O(mn)
Remark: 简单题。最长公共子串。

Explanation:
尝试考虑以B[i]结尾的B[:i+1]子串和A串的关系，迭代A，若A[j] == B[i]，那么比较内部的串。
即状态方程： dp[i][j] = dp[i-1][j-1] + 1 if B[i] == A[j]

Code:

def findLength(self, A, B):
    n1, n2 = len(A), len(B)
    dp = [[0] * (n1+1) for _ in range(n2+1)]
    res = 0
    for i in range(1, n2+1):
        for j in range(1, n1+1):
            if B[i-1] == A[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                res = max(res, dp[i][j])     
    return res

Day13

Date: 18-09-25

494-M

494. Target Sum
>Difficulty：★★★★☆
Beats: 49.57%
Time Complexity: ?
Remark: dp + dfs，这里的dp的自顶向下算法就是dfs，但是需要做memorization，否则会出现TLE。

Explanation:
以第i位置，以及可能在这个位置出现的和，两个值的tuple作为key，节约时间空间。

Code:

def findTargetSumWays(self, nums, S):
    def memoization(i, S):
        if i == 0:
            return 1 if S == 0 else 0
        elif (i,S) in dic:
            return dic[i, S]
        res = memoization(i-1, S-nums[i-1]) + memoization(i-1, S+nums[i-1])
        dic[i, S] = res
        return res
    dic = {}
    return memoization(len(nums), S)

Day12

Date: 18-09-24

516-M

516. Longest Palindromic Subsequence
>Difficulty：★★★☆☆
Beats: \
Time Complexity: O(n^2)
Space Complexity: O(n^2)
Remark: 要么就是python3的执行评判有问题，要么就是python3的执行是真的慢。算法的想法挺简单的，属于那种制表就可以完成的。

Explanation:
我们假设从i位置开始，长度为l的子串subs（这里是子串，不是子序列），现在需要判断subs的最长回文子序列，先判断首尾是否相同：相同则首尾同时向内缩进1位，继续判断。 自底向上的做法，需要我们将长度l从2一直迭代至len(s)。

Formula:
T[i][j] = T[i+1][j-1] + 2 if s[i] == s[j] else max(T[i+1][j], T[i][j-1])

Code:

# submit this using python, not python3
def longestPalindromeSubseq(self, s):
    n = len(s)
    dp = [[0]*n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1
    for l in range(2, n+1):
        for i in range(0, n - l + 1):
            j = i + l - 1
            if l == 2 and s[i] == s[j]:
                dp[i][j] = 2
            elif s[i] == s[j]:
                dp[i][j] = dp[i+1][j-1] + 2
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
    return dp[0][-1]

Day11

Date: 18-09-23

120-M

120. Triangle >Difficulty：★★★☆☆
Beats: 72.33%
Time Complexity: O(n^2)
Space Complexity: O(n)
Remark: 标准DP问题。

Explanation:
- Step1: 判断
最小化问题，满足两个性质，可以用DP解。

  • Step2: 状态
    首先我们不可能从底向上，从最后一层最小的点往上找的。
    这样的话，就会想知道，比如到第k层第i个元素，想知道到前k-1层第i/i-1个元素那里哪一个最小。
    所以状态可以定义为到第k层第i个元素

  • Step3: 状态方程 我们需要迭代整个n，去寻找[start, end]的分割位置k，在k位置的时候，计算它的最坏情况，即max(dp[start, k-1], dp[k+1, end]) + k，现在我们想要的最终结果就是所有这样的k中最小的。

  • Step4: Tabulation or Memorizatio
    有两种做法，一种是存储N个结果，另一种是直接修改原数组。

    def minimumTotal(self, triangle):
# res = [0]*len(triangle)
# res[0] = triangle[0][0]
for i in range(1, len(triangle)):
    # cur = [x for x in res]
    for j in range(len(triangle[i])):
        if j-1 < 0:
            upmin = triangle[i-1][j]
        elif j >= len(triangle[i-1]):
            upmin = triangle[i-1][j-1]
        else:
            upmin = min(triangle[i-1][j], triangle[i-1][j-1])

        triangle[i][j] += upmin
    # print(res)
return min(triangle[-1])

Day10

Date: 18-09-22

375-M

375. Guess Number Higher or Lower II
>Difficulty：★★★☆☆
Beats: 15.63%
Time Complexity: O(n^2)
Remark: 题目表述有点晦涩。又是可以用两个数字表示字典key的一道题。

Explanation:源: xuehaohu
- Step1: 判断
最后我们需要找出how much money you need to have to guarantee a win，保证赢，至少需要多少钱，看起来像是需要最大化某个量又需要最小化另外某个量的问题。

  • Step2: 状态
    如果只有一个数，那么不用猜，代价是0；

如果有两个数，比如[5, 6]，最小的代价是5：我们有两种方法去猜，一是猜5，猜中代价为0，猜不中代价为5，这种情况下需要付出的代价是5（想一想为什么）；另一种是猜6，猜中代价为0，猜不中代价为6。综合两种情况，猜中的最小代价是5;

如果有三个数，比如[3, 4, 5]，我们猜中的最小代价一定是4。

以此类推，对于更大的范围，我们可以将其划分成多个小的范围，这就符合DP问题的定义了。 我们可以定义状态为从start到end需要付出的最小代价。

  • Step3: 状态方程 我们需要迭代整个n，去寻找[start, end]的分割位置k，在k位置的时候，计算它的最坏情况，即max(dp[start, k-1], dp[k+1, end]) + k，现在我们想要的最终结果就是所有这样的k中最小的。

  • Step4: Tabulation or Memorizatio

Code:

def getMoneyAmount(self, n):
    dp = {}
    def getMA(l, r):
        if l > r:
            return 0
        if (l, r) in dp:
            return dp[l, r]
        if r == l:
            dp[l, r] = 0
            return dp[l, r]
        if r-l == 1:
            dp[l, r] = l
            return dp[l, r]
        dp[l, r] = r*r
        for i in range(l, r):
            dp[l, r] = min(dp[l,r], i + max(getMA(l, i-1),getMA(i+1, r)))
        return dp[l, r]
    return getMA(1, n)

Day9

Date: 18-09-21
数值分析上到今天终于跟不上了，看来假期需要补一补了，不然就真废了。今天的组会开的很不尽兴，各种事故。

712-M

712. Minimum ASCII Delete Sum for Two Strings
>Difficulty：★★★★☆
Beats: 11.11%
Time Complexity: O(n^2)
Remark: 思路较为简单。本题基于最长公共子序列的解法，只不过状态的内容由公共子序列的长度变成了需要删除字母的代价。
Explanation:
- Step1: 判断
最小化删除的字母和，是DP问题

  • Step2: 状态
    匹配到str1[j]和str2[i]需要删除的代价，即str1[:j]和str2[:i]需要删除的字母ascii码和，设为dp[i][j]。

  • Step3: 状态方程
    由状态之间的传递关系，如果str1[j] == str2[i] ，那么它们俩可以不用删除，需要考虑的是str1[:j-1], str2[:i-1]这两个串之间的关系，它们的关系由dp[i-1][j-1]给出；
    如果str1[j]和str2[i]不同，直观想法是把这两个字符都删除了，但这样需要付出的代价无疑是 最大的（dp[i-1][j-1] + str2[i] + str1[j]），考虑，如果只删除str1[j]，那么问题转化为str1[:j-1]和str2[:i]进行匹配，它们需要付出的代价就是dp[i][j-1] + str1[j]，同理，删除str2[i]需要付出的代价 是dp[i-1][j] + str2[i]，二者取较小者即可。所以状态方程定义如下：
    if str1[j] == str2[i]: dp[i][j] = dp[i-1][j-1]
    if str1[j] != str2[i]: dp[i][j] = max(dp[i][j-1] + str1[j],dp[i-1][j] + str2[i])

  • Step4: Tabulation or Memorizatio
    实现的时候，为了计算方便，多增加一行一列。

Code:

def minimumDeleteSum(self, s1, s2):
    l1, l2 = len(s1), len(s2)
    dp = [[0]*(l1 + 1) for _ in range(l2 + 1)]
    for i in range(1, l1+1):
        dp[0][i] += dp[0][i-1] + ord(s1[i-1])
    for i in range(1, l2+1):
        dp[i][0] += dp[i-1][0] + ord(s2[i-1])

    for i in range(1, l2+1):
        for j in range(1, l1+1):
            if s2[i-1] == s1[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = min(dp[i-1][j] + ord(s2[i-1]), dp[i][j-1] + ord(s1[j-1]))
    return dp[l2][l1]

Day8

Date: 18-09-20
失了智的一天，两道题没有一道想出来的。差评，菜🐶。这两道题属于同一类型的，值得再刷！

813-M

813. Largest Sum of Averages
>Difficulty：★★★★☆
Beats: <20%
Time Complexity: O(Kn^2)
Remark: 如果没有直接思路，从笨方法入手深入理解题意，然后再想想哪里可以提升。

Explanation:(参考lee215的题解)
如何寻找状态？
我们有一个数组，至多可以分成K个连续的部分，然后对每个部分求平均再累加，求这个最大值。
K个连续的部分，如何分割呢，我们可以以每个部分最后一个元素的位置作为分割点（至于为什么这么想，因为标志位置就只有每部分的开头和结尾元素，二者选其一而已）。
现在假设我们分割了倒数一部分元素，那么整个数据集被我们分割成了最后一部分，以及前面k-1个部分，那么它的值便可以用下面的式子表达：
dp[n,k] = max(dp[n, k], dp[i, k-1] + sum(A[i:n])/float(n-i)), i=n-1,...,0
由此可以用递归求解本题。
(PS: lee215是真的喜欢用set的key来保存状态（：).

Code:

def largestSumOfAverages(self, A, K):
    memo = {}
    def search(n, k):
        if (n, k) in memo: return memo[n, k]
        if n < k: return 0
        if k == 1:
            memo[n, k] = sum(A[:n]) / float(n)
            return memo[n, k]
        cur, memo[n, k] = 0, 0
        for i in range(n - 1, 0, -1):
            cur += A[i]
            memo[n, k] = max(memo[n, k], search(i, k - 1) + cur / float(n - i))
        return memo[n, k]
    return search(len(A), K)

873-M

873. Length of Longest Fibonacci Subsequence
>Difficulty：★★★★☆
Beats: 73.98%
Time Complexity: O(n^2)
Remark: 如果DP的掌握程度可以量化的话，我觉得我才走到25%，状态和状态转移方程真TM神奇，同时也明确提醒自己状态不一定连续。

Explanation:(参考lee215的题解)
首先我们明确一点，已知类斐波那契数列的连续两个数之后，可以推导出规定范围内所有属于它的数。
基于这一点，我们的状态可以基于类斐波那契数列的连续两个数来设置，即令dp[a, b]表示以数(a, b)为结尾的类斐波那契数列。
如此，我们的状态方程可以设置为：dp[a, b] = (dp[b-a, a] + 1) or 2。

Code:

def lenLongestFibSubseq(self, A):
    dp = collections.defaultdict(int)
    s = set(A)
    res = 0
    for j in xrange(len(A)):
        for i in xrange(j):
            if A[j] - A[i] < A[i] and A[j] - A[i] in s:
                dp[A[i], A[j]] = dp.get((A[j] - A[i], A[i]), 2) + 1
                res = max(res, dp[A[i], A[j]])
    return max(dp.values() or [0])

Week1

Solved 18 problems.

Day7

Date: 18-09-19

064-M

64. Minimum Path Sum
>Difficulty：★★☆☆☆
Beats: 48.92%
Time Complexity: O(n^2)
Remark: 属于比较简单的基础DP题，模拟一遍就知道状态方程了。

Explanation:
状态定义为走到当前位置需要的最少步数dp[i][j]。
由规则可知，当前步往下一步走，只能向下或者向右，因此可以推得状态方程：
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。

Code:

class Solution:
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        n = len(grid)
        m = len(grid[0])
        dp = [[0]*m for _ in range(n)]
        dp[0][0] = grid[0][0]
        for i in range(1,m):
            dp[0][i] = dp[0][i-1] + grid[0][i]
        for i in range(1,n):
            dp[i][0] = dp[i-1][0] + grid[i][0]
        # print(dp)
        for i in range(1, n):
            for j in range(1, m):
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
        # print(dp)
        return dp[n-1][m-1]

300-M

300. Longest Increasing Subsequence
>Difficulty：★★☆☆☆
Beats: 11.25%
Time Complexity: O(n^2)
Remark: 十分典型的DP题，求最长递增子序列。

Explanation:
定义状态为在第i个元素时以它结尾的最长递增子序列的长度T[i]。
求解T[i]时，我们需要寻找前i个元素中比nums[i]小的最大T[k]。
则状态方程为：

Code:

py class Solution: def lengthOfLIS(self, nums): “”” :type nums: List[int] :rtype: int “”” if not nums: return 0 n = len(nums) res = [1]*n for i in range(n): tmp = res[i] for j in range(i-1, -1, -1): if nums[j] < nums[i]: tmp = max(tmp, res[j] + 1) res[i] = tmp return max(res)

<hr/>

#### 416-M  
[416. Partition Equal Subset Sum](https://leetcode.com/problems/partition-equal-subset-sum/description/)  
>Difficulty：★★★☆☆     
Beats: 0%   
Time Complexity: O(n^2)  
Remark: 我觉得这题python的判法有问题，同样的思路，复杂度，我递归和制表两种方法都试了，疯狂TLE，太真实了。  

Explanation:  
这题的思路相对简单，要将数据集划分为两个和相等的的子数据集，那么和`sum`肯定是偶数，奇数和直接返回错。  
这个时候问题转化为，求`subset sum`，指定`sum`，是否存在子集满足和等于它。  

对于`subset sum`这个问题，比较经典。  
<pre>
Let isSubSetSum(int set[], int n, int sum) be the function to find whether there is a
subset of set[] with sum equal to sum. n is the number of elements in set[].

The isSubsetSum problem can be divided into two subproblems
…a) Include the last element, recur for n = n-1, sum = sum – set[n-1]
…b) Exclude the last element, recur for n = n-1.
If any of the above the above subproblems return true, then return true.
</pre>

这题贴没AC的代码，看同样的思路改写成C++有没有问题🙃  
Code:

py class Solution: def canPartition(self, nums): “”” :type nums: List[int] :rtype: bool “”” nsum = sum(nums) if nsum % 2 == 1: return False n = len(nums) half = int(nsum/2)

    def subsetSum(target, ns):
        if target == 0: return True
        if not ns: return False
        if ns[-1] > target:
            return subsetSum(target, ns[:-1])
        return subsetSum(target-ns[-1], ns[:-1]) or subsetSum(target, ns[:-1])

    return subsetSum(half, nums)

    # dp = [[0]*(half+1) for _ in range(n)]
    # for i in range(n):
    #     dp[i][0] = 1
    # for i in range(1, half+1):
    #     if i == nums[0]:
    #         dp[0][i] = 1
    # for i in range(1, n):
    #     for j in range(1, half+1):
    #         if j < nums[i]:
    #             dp[i][j] = dp[i-1][j]
    #         else:
    #             dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i]]
    # if dp[n-1][half]:
    #     return True
    # return False  
<hr/>

### Day6  
**Date: 18-09-18**  

#### 343-M
[343. Integer Break](https://leetcode.com/problems/is-subsequence/description/)  
>Difficulty：★★☆☆☆     
Beats: 36.83%   
Time Complexity: O(n^2)  
Remark: 这道题属于容易推断的DP问题，多举几个例子就能自己发现了。  

Explanation：  
通过枚举观察可以发现以下结果：  
<pre>
2: 1
3: 1x2 = 2
4: 2x2 = 4
5: 2x3 = 6
6: 3x3 = 9
7: 3x4 = 12
8: 2x(6) = 2x9 = 18
9: 3x(6) = 3x9 = 27
10: 2x(8) = 2x18 = 36
</pre>
所以它具有最优子结构以及重复子问题的性质。值得注意的是，2和3的结果并没有他们本身大，所以后续我们需要用到2或者3的时候，我们用的是它本身，而不是它break的结果。  

状态方程如下：  
`T[n]=max(T[n], T[i]*T[n-i]) i = 1,...,n/2`  

Code:

py class Solution: def integerBreak(self, n): “”” :type n: int :rtype: int “”” if n < 4: return n-1 maxr = [0, 1, 2, 3] for cur in range(4, n+1): cm = 0 for i in range(1, int(cur/2) + 1): cm = max(cm, maxr[i] * maxr[cur-i]) maxr.append(cm) return maxr[n]

<hr/>

#### 474-M
[474. Ones and Zeroes](https://leetcode.com/problems/ones-and-zeroes/description/)  
>Difficulty：★★★☆☆     
Beats: 15.76%   
Time Complexity: O(n)  
Remark: 就题目本身而言，属于经典的0/1背包问题，而且属于二维费用的背包问题。同时这题揭露了LeetCode中python3和python评判的差异，同样的代码，python3用时更久。  

Explanation:  
先Mark一下，状态方程很简单：`dp[i][j] = max(dp[i][j], dp[i-zeros][j-ones]+1)`  
留待背包问题做个总结。  

Code:

py

使用python，可AC；使用python3，TLE

class Solution: def findMaxForm(self, strs, m, n): “”” :type strs: List[str] :type m: int :type n: int :rtype: int “”” dp = [[0] * (n+1) for _ in range(m+1) ] for s in strs: s0 = s.count(‘0’) s1 = len(s) - s0 for i in range(m, s0-1, -1): for j in range(n, s1-1, -1): dp[i][j] = max(dp[i][j], dp[i-s0][j-s1]+1)

    return dp[m][n]
<hr/>

#### 392-M
[392. Is Subsequence](https://leetcode.com/problems/is-subsequence/description/)
>Difficulty：★★★☆☆     
Beats: 62.02%   
Time Complexity: O(nm)  
Remark: 中规中矩的DP，但是构建状态矩阵的时候MLE了两次，之后改用了递归。

Explanation:  
- *Step1: 判断*  
满足重叠子问题、最优子结构性质。

- *Step2: 状态*  
首先明确一点，如果一个串B是串A的子串，那么串B中字符出现的先后顺序在串A中也是一样的。想一想为什么？  
在知道了上面一这点后，我们可以这样定义状态，若当前字符s[i]对应串A的A[j]，其状态为`true`。  

- *Step3: 状态方程*  
那么s[i+1]在哪里找呢？我们需要在A[j+1:]里找，重复上面的过程。如果有一次s[k]没有找到对应字符，直接返回`false`。

- *Step4: Tabulation or Memorizatio*    
这里我用的是自上而下的递归。  

Code:

py class Solution: def isSubsequence(self, s, t): “”” :type s: str :type t: str :rtype: bool “”” def sub(s, t): if not s: return True if not t: return False target = s[0] idx = -1 for i in range(len(t)): if target == t[i]: idx = i break if idx < 0: return False return sub(s[1:], t[idx+1:]) return sub(s, t)

# 利用Python自带函数  
def isSubsequence(self, s, t):
    ind = -1
    for i in s:
        try: ind = t.index(i,ind+1)
        except: return False
    return True
<hr/>

### Day5  

**Date: 18-09-17**  

#### 357-M  
[357. Count Numbers with Unique Digits](https://leetcode.com/problems/count-numbers-with-unique-digits/description/)  

>Difficulty：★★☆☆☆     
Beats: 69.17%   
Time Complexity: O(n)  
Remark: 简单题，可以总结为数学问题，这道题说明，状态不一定要直接解决我们的最终问题，它可以是最终答案的骨架。  

一看就懂，直接放代码。
Code:

py

n = 1 : 10

n = 2 : 9 * 9 (1-9)|(0-9 except first Digit)

n = 3 : 9 * 9 * 8 (1-9)|(0-9 except first Digit) | (0-9 except first Digit))

…

class Solution: def countNumbersWithUniqueDigits(self, n): “”” :type n: int :rtype: int “”” if n == 0: return 1 if n == 1: return 10 dp = [0]*(n+1) dp[1] = 10 dp[2] = 9*9 for i in range(3, n+1): dp[i] = dp[i-1] * (10-i+1) return sum(dp)

<hr/>

### Day4  

**Date: 18-09-16**  

#### 714-M  

[714. Best Time to Buy and Sell Stock with Transaction Fee](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/)  

>Difficulty：★★★★☆     
Beats: 44.97%   
Time Complexity: O(n)  
Remark: 比较难，什么状态，以及状态方程。我个人想不到需要两个状态方程来维护，所以看了很多题解。买卖这两个字很值得推敲。  

Explanation:  
有两个题解写的比较好，推荐一下。  
[精简的解释](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/discuss/136388)  
[利用状态机，含图解，非本题](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/discuss/75928/)  
[针对买卖股票系列，总结十分全面](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/discuss/108870/)  

本题的关键就是要想清楚什么时候买、什么时候卖。这二者又取决于今天 买/卖 和明天 买/卖 有什么联系。  

买和卖之间的桥梁就是股票以及利润。  

以`1, 4, 2, 8, 4, 9`为例。  
第0天，假设不买，则利润为`profit[0] = 0`；假设买了，持有`shares[0] = -1`。  
第1天，根据第0天的两种状态：  
今天卖还是不卖呢，可以卖手中持有的，如果卖，收益是 `tmp = shares[0] + nums[1] - fee`，这里结果是1，如果不卖，收益就是`profit[0]=0`，说明今天卖昨天买的可以有正收益，因此`profit[1] = max(tmp, profit[0])`；  
那么今天适不适合买呢，如果买，就面临一个选择。因为要求不能持有多余一股，所以今天买了，昨天就不能买。因此，若今天买，需要付出`tmp = profits[0] - nums[1] = -4`，显然第0天买更划算，因此`shares[1] = max(tmp,  shares[0])`。  
……  
以此类推，可以理解为：  
>`dp[i][0]`: arrive i, no shares at hand.
`dp[i][1]`: arrive i, shares at hand.
`dp[i][1] = max(dp[i-1][0] - nums[i], dp[i-1][1])`: buy at nums[i] or do nothing.
`dp[i][0] = max(dp[i-1][1] + nums[i] - fee, dp[i-1][0])`: sell at nums[i] or do nothing.  


Code:

py class Solution: def maxProfit(self, prices, fee): “”” :type prices: List[int] :type fee: int :rtype: int “”” # dp = [[0 for _ in range(2)] for _ in range(len(prices))] # dp[0][0] = 0 # dp[0][1] = -prices[0] # for i in range(1, len(prices)): # dp[i][1] = max([dp[i - 1][0] - prices[i], dp[i - 1][1]]) # dp[i][0] = max([dp[i - 1][1] + prices[i] - fee, dp[i - 1][0]]) # print(dp) # return dp[-1][0]

    profits = 0
    shares = -prices[0]
    for i in range(1, len(prices)):
        tmp_shares = shares
        shares = max(profits - prices[i], shares)
        profits = max(tmp_shares + prices[i] - fee, profits)
    return profits   
<hr/>

#### 647-M
[647. Palindromic Substrings](https://leetcode.com/problems/palindromic-substrings/description/)  
>Difficulty：★★★☆☆     
Beats: 29.16%   
Time Complexity: O(n^2)  
Remark: 关键还是要分析出相邻状态之间的关系。  

Explanation:  
- *Step1: 判断*  
满足重叠子问题、最优子结构性质。考虑如果某个串是回文串，那么它所临近的串应该如何判断呢？

- *Step2: 状态*  
直观一点，我们可以简单的认为状态是从`i`到`j`的子串是否是回文串，即`T[i][j]`是否是回文串。


- *Step3: 状态方程*  
假设现在`T[i][j]`是回文串，对于`s[j+1]`，基于回文串的性质，我们知道，如果在已有回文串的两边加上同样的字符，它依然是一个回文串，所以若`s[i-1]`和`s[j+1]`相等，就可以得出`T[i-1][j+1]`也是回文串。所以我们可以推导出状态方程：  
`if s[i]==s[j]: T[i][j] = T[i+1][j-1]`  


- *Step4: Tabulation or Memorizatio*   
本题我们的父问题需要多个子问题堆叠，比较简单的想法是自底向上，构建二维状态矩阵。  

Code

py class Solution: def countSubstrings(self, s): “”” :type s: str :rtype: int “”” if not s: return 0 n = len(s) T = [[None] * n for _ in range(n)] res = 0 for l in range(n): for i in range(n): j = i+l if j < n: if i == j: T[i][j] = 1 res += 1 continue if s[i] == s[j]: if j-1 <= i+1 or T[i+1][j-1] == 1: T[i][j] = 1 res += 1 return res

<hr/>


#### 877-M  

[877. Stone Game](https://leetcode.com/problems/stone-game/discuss/)  
>Difficulty：★★★☆☆     
Beats: %   
Time Complexity: O(n)  
Remark: 可以说没有意义。  

Alex永远不会输。

<hr/>

### Day3  

**Date: 180915**  

#### 413-M  

[413. Arithmetic Slices](https://leetcode.com/problems/arithmetic-slices/description/)  
>Difficulty：★★★☆☆     
Beats: 97.54%   
Time Complexity: O(n)  
Remark: 有几个点需要注意一下，按照DP的解题思路，想通了注意点就ok了。  

Explanation:  
- *Step1: 判断*  
满足重叠子问题、最优子结构性质。即如果某个位置与之前连续的若干个元素满足题意，那么其下一个位置是否满足呢？  

- *Step2: 状态*  
假设`A[i]`与之前若干个连续元素满足arithmetic slices的性质 (i>=2)，我们将之前的满足条件的连续元素存到数组中。  
那么元素`A[i+1]`是否满足，只需要比较它和它之前的两个元素即可。  
如果`A[i+1]`满足，会多出多少个满足条件的arithmetic slices呢？  
如果`A[i+1]`不满足，又要怎么算呢？


- *Step3: 状态方程*  
接上面的状态分析。  
举个简单的例子，`1,3,5,7`是满足性质的一个slice，判断元素`9`，`9-7==7-5`，
那么对于`1,3,5,7,9`而言，因为它整体是满足条件的，所有以`9`结尾的所有至少3个连续元素都可以满足题目条件，
即`3,5,7,9`，`5,7,9`均满足，整理一下：  
<pre>
1,3,5,7,9  
3,5,7,9  
5,7,9  
</pre>
 所以当多出一个元素`9`满足条件的时候，就有多出`5-3+1`个元素。

 注意点，如果`A[i+1]`不满足，我们也不能从`A[i+1]`重新开始算，而是需要从`A[i]`开始重新算。  

- *Step4: Tabulation or Memorizatio*   


Code:

py class Solution: def numberOfArithmeticSlices(self, A): “”” :type A: List[int] :rtype: int “”” cur = [] res = 0 for i in range(len(A)): if len(cur) < 2: cur.append(A[i]) else: if A[i] - cur[-1] == cur[-1] - cur[-2]: cur.append(A[i]) res += len(cur) - 3 + 1 else: tmp = cur[-1] cur = [tmp, A[i]] return res

<hr>

### Day2
**Date: 18-09-14**  

#### 338-M  

[338. Counting Bits](https://leetcode.com/problems/counting-bits/description/)  
>Difficulty：★★★☆☆     
Beats: 63.94%   
Time Complexity: O(n)  
Remark: 考察二进制的时候，多向左移右移的方向考虑。  

Explanation:  
- *Step1: 判断*  
朝`O(n)`的时间复杂度方向考虑，肯定需要用到子问题的解，不然不太可能。  

- *Step2: 状态*  
状态自然是数`i`的二进制中包含1的个数`count[i]`。  
难度是如何找寻它与子问题的关系。  

- *Step3: 状态方程*  
<pre>
0: 0000 0000   0
1: 0000 0001   1
2: 0000 0010   1
3: 0000 0011   2
4: 0000 0100   1
5: 0000 0101   2
6: 0000 0110   2
7: 0000 0111   3
8: 0000 1000   1
</pre>
观察`0-8`的二进制，会比较自然的朝左移右移的角度去想。一个数的二进制左移一位相当于翻倍，反之减小一般。奇数比较特别的地方在于左移的时候末尾补`0`，右移的时候原来末尾的`1`会丢失。基于这个想法，对于数`i`，在不考虑原本末位的情况下，我们不难想到右移后`i`与`i>>1`的二进制中含有相同个数的`1`。再加上末位可能有的`1`，就可以得到`i`中含有`1`的个数了。  
得到状态方程：`count[i] = count[i>>1] + (i & 1)`

- *Step4: Tabulation or Memorizatio*   
两种方法都可以。  


Code:

python class Solution: def countBits(self, num): “”” :type num: int :rtype: List[int] “”” array = [0]*(num+1) for i in range(num+1): array[i] = array[i>>1] + (i & 1) return array

<hr>

#### 053-E  

[053 Maximum Subarray](https://leetcode.com/problems/maximum-subarray/description/)  
>Difficulty：★★☆☆☆     
Beats: 99.53%   
Time Complexity: O(n)  
Remark: `O(n^2)`是不行的，从解DP问题的一般思路入手，一步一步来。同样的Beats存在问题，以后除了低于30%的就不写了，另外两个数比较大小，python的`max`函数比直接比较要慢。  

Explanation:  
- *Step1: 判断*  
最大子串问题，属于DP问题。  

- *Step2: 状态*  
我们希望得到的`Maximum Subarray`，这个子串的最后一个元素可能在原数组中的任意位置，因此自然联想到用**以`i`结尾的子串的最大和`res[i]`** 作为状态，当然，这个子串可能不是以`0`作为首元素。  

- *Step3: 状态方程*  
探索`res`的前后序列关系，如果`res[i-1]`是前`i-1`个元素的最大和，那么在第`i`个元素的位置，我们需要计算以它结尾的最大和，如果`res[i-1] < 0`，那就没有累加的必要，反之，累加。即状态方程为：  
`res[i] = max(0, res[i-1]) + nums[i]`  
更新最大值。

- *Step4: Tabulation or Memorizatio*   
两种方法都可以，为了节约空间，我们只使用常数数量的空间。

Code:

python class Solution: def maxSubArray(self, nums): “”” :type nums: List[int] :rtype: int “”” res = cur = nums[0] for i in range(1, len(nums)): if cur <= 0: cur = nums[i] else: cur += nums[i] if cur > res: res = cur return res

<hr>

#### 303-E  

[303. Range Sum Query - Immutable](https://leetcode.com/problems/range-sum-query-immutable/description/)  
>Difficulty：★☆☆☆☆  
Beats: 87.5%   
Time Complexity: O(n)  
Remark: 简单题，基于一个简单的发现。同样的Beats存在问题。  

Explanation:  
1. *Step1: 判断*  
求从位置i到位置j的值的和，i和j任意，具有重叠子问题、最优子结构两个性质。  

2. *Step2: 状态*  
如果暴力把所有的i,j都算一遍，那么无论时间还是空间复杂度都会很高。  
换个思路，我们算一下从0到1，两个数的和`sum[1]`是`nums[0]+nums[1]`，
从0到2的和`sum[2]`是`nums[0] + nums[1] + nums[2]`，
从0到3的和`sum[3]`是`nums[0] + nums[1] + nums[2] + nums[3]`。  
我们发现从0开始，加到`i-1`的和是`sum[i-1]`，到`i`的时候，只需要在`sum[i-1]`的基础上加上`nums[i]`，
在`sum[i-2]`的基础上加上`nums[i-1] + nums[i]`……  

3. *Step3: 状态方程*  
那么我们的状态就可以设置为从0到i的和是`sum[i]`。  
从`i`到`j`的话，`sum[j]`就等于`sum[i] + nums[i+1] + ... + nums[j]`。  
从而得到`res[i,j] = sum[j] - sum[i]`。

4. *Step4: Tabulation or Memorizatio*   
根据题目的设置，可以选用`list`或者`dict`。

Code:

python class NumArray:

def __init__(self, nums):
    """
    :type nums: List[int]
    """
    self.val = {-1:0}
    for i in range(len(nums)):
        self.val[i] = self.val[i-1] + nums[i]

def sumRange(self, i, j):
    """
    :type i: int
    :type j: int
    :rtype: int
    """
    return self.val[j] - self.val[i-1]
<hr>  

#### 198-E
[198. House Robber](https://leetcode.com/problems/house-robber/description/)  
>Difficulty：★☆☆☆☆  
Beats: 50% ? 100%   
Time Complexity: O(n)  
Remark: 同样是Python，时间复杂度相同，常数空间复杂度的解居然也只有50%，对比了其他人的解法，感觉leetcode的评判有点问题。  

Explanation:  
1. *Step1: 判断*  
最大化数值，是DP问题  

2. *Step2: 状态*  
在第i家可以获得的最大利润P[i]，不一定要取nums[i]

3. *Step3: 状态方程*  
P[i] 和同序列之前的数有什么关系呢？  
我们知道为了在第i家的时候，有两种选择：  
    + 一是偷取第i家，此时最大利润是`P[i-2] + nums[i]`  
    + 二是不取第i家，此时最大利润就是`P[i-1]`  

  为了使得在第i家时的利润最大，我们取二者较大的。因此可以求得状态方程：  
`P[i] = max(P[i-1], P[i-2] + nums[i])`。

4. *Step4: Tabulation or Memorizatio*   
这里结合`746-E`里的做法，可以节约空间，只使用常数空间复杂度。

Code:

python class Solution:
def rob(self, nums): “”” :type nums: List[int] :rtype: int “”” length = len(nums) if not nums: return 0 if length == 1: return nums[0]

    pre, cur = nums[0], max(nums[0], nums[1])
    for i in range(2, length):
        pre, cur = cur, max(cur, pre + nums[i])
    return cur
<hr>

### Day1
**Date: 18-09-13**  

#### 746-E  
[746. Min Cost Climbing Stairs](https://leetcode.com/problems/min-cost-climbing-stairs/description/)  
>Difficulty：★☆☆☆☆  
Beats: 52% / 100%   
Time Complexity: O(n)  
Remark: 简单题，斐波那契的拓展，但是同样是BottomUp，用了O(n)的空间，和O(1)的空间是不同的！  

Explanation:  
参考070题，再加上cost的条件，注意要踏到最顶端，容易得出状态是**迈上**第i层的最小代价T[i]。  
要踏上第`i`层，可能是从`i-1`或者`i-2`层上来的，要使得代价最小，那么二者取较小者。  
因此有状态方程：`T[i] = min(T[i-1], T[i-2]) + cost[i]`。  
时间复杂度都是`O(n)`，不难写出代码。下面分享的是两种用不同空间复杂度的代码。  

**空间复杂度 O(n)** - 这是比较常规的做法

python class Solution: def minCostClimbingStairs(self, cost): “”” :type cost: List[int] :rtype: int “”” if not cost: return 0 n = len(cost) + 2 T = [0]*n T[0] = 0 T[1] = 0 for i in range(2, n): T[i] = min(T[i-1], T[i-2]) + cost[i-2] print(T) return min(T[n-1], T[n-2])

**空间复杂度 O(1)**

python class Solution: def minCostClimbingStairs(self, cost): “”” :type cost: List[int] :rtype: int “”” if not cost: return 0 pre, cur = cost[0], cost[1] for i in range(2, len(cost)): pre, cur = cur, min(pre, cur) + cost[i] return min(pre,cur)

注意这里的`pre, cur = cur, min(pre, cur) + cost[i]`，其作用等价于：

python tmp = cur cur = min(pre, cur) + cost[i] pre = tmp

<hr>

#### 121-E
[121. Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/)  
>难易程度：★★☆☆☆  
Beats: 73.94%  
时间复杂度：O(n)  
Remark: 简单题，有助于DP基本概念的理解。

Explanation:  
暴力：
每一天都和前面所有天的股价计算差值，保留最大值，那么时间复杂度就是 n的平方。不出意外就是TLE了。

问题在于如何确定哪天是股价最小的，再确定差价最高的。

**DP Steps**  
- *Step1: 判断*  
最大化利润，是DP问题  

- *Step2: 状态*  
第i天可以获得的最大利润P[i]（不一定是第[i]天卖出）

- *Step3: 状态方程*  
P[i] 和 P[i-1]有什么关系呢？  
如果s[i] 比s[i-1]小，那么P[i] = P[i-1]，同时这两天最小价格至少会是s[i]，更新minPrice；  
如果s[i] 比s[i-1]大，那么第s[i] - minPrice 是要比s[i-1] - minPrice大的，因此更新当前差价，和最大差价比较，如果比最大差价大，那么P[i] = nowMax

- *Step4: Tabulation or Memorizatio*  
Code:

python class Solution: def maxProfit(self, prices): “”” :type prices: List[int] :rtype: int “”” if not prices: return 0 n = len(prices) T = [0] minPrice = prices[0] maxPrice = T[0] for i in range(1, n): if prices[i] < prices[i-1]: T.append(T[i-1]) minPrice = prices[i] if prices[i] < minPrice else minPrice else: cur = prices[i] - minPrice maxPrice = cur if cur > maxPrice else maxPrice T.append(maxPrice) return T[n-1]

<!-- <hr style="border:none; border-top:1px dashed ; height:1px"/> -->
<hr/>

#### 070-E  

[070. Climbing Stairs](https://leetcode.com/problems/climbing-stairs/description/)  
>难易程度：★☆☆☆☆  
TopDown Beats: 100%  
BottomUp Beats: 45.20%
时间复杂度：O(n)  
Remark: 简单题，理解TopDown和BottomUp概念，[区别](https://www.geeksforgeeks.org/tabulation-vs-memoizatation/)。  


DP问题中有一些典型的情况。  
本题属于其中一种，即斐波那契数列。  
那么不难想到状态方程`T[n] = T[n-1] + T[n-2]`。  

假设我们没看出这是一个斐波那契问题，我们来推理看看。

(层数)：方式。解释  
 (1)： 1。只有一种方式  
 (2)： 2。两种方式，11，2。  
 (3)： 3。111，12，21。  
 (4)： 5。1111，112， 121，211，22。  

思考一下4层的情况，如果先迈出了一步，那么总的情况就是1(3)，括号里是剩下的总层数，3层的情况我们已经算过了，把3层的情况填到括号中，1(111)，1(12)，1(21)；同理如果先迈出两步，总的情况就是2(2)，(2)又有2种。那么(4)可以写成`(4) = 1(3) + 2(2)`。下面验证一下(5)。  
(5) => 1(4)，2(3) => 1(1111，112， 121，211，22)，2(111，12，21)。  

这个时候我们就可以得出相同的结论了。

这道题的价值在于练习`TopDown` 和 `BottomUp` 两种方式。    

**Top Down**

python class Solution: def climbStairs(self, n): “”” :type n: int :rtype: int “”” f = [0] * (n+1) f[0] = f[1] = 1 for i in range(2, n+1): f[i] = f[i-1] + f[i-2] print(f) return f[n]

**Bottom Up**

python class Solution: def climbStairs(self, n): “”” :type n: int :rtype: int “”” lookup = [None]*(n+1)

    # Memoization -> Bottom Up
    def fib(n):
        if n == 0 or n == 1:
            lookup[n] = 1
        if lookup[n] is None:
            lookup[n] = fib(n-1) + fib(n-2)
        return lookup[n]
    res = fib(n)
    # print(lookup)
    return res

```