674.

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        max_l = 1
        l = 1
        for i in range(1,len(nums)):
            if nums[i] <=nums[i-1]:
                l = 1
            else:
                l += 1
                max_l = max(max_l,l)
        return max_l

300.

错误代码：

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 1:
            return n
        DP = [1]*n
        for i in range(0,n-1):
            for j in range(0,i):
                if(nums[i]>nums[j]):
                    DP[i] = max(DP[i],DP[j]+1)
        return max(DP[:])

存在的问题：DP[i] 应该需要从1循环到n-1。DP[0] = 1

正确代码：

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 1:
            return n
        DP = [1]*n
        for i in range(1,n):
            for j in range(0,i):
                if(nums[i]>nums[j]):
                    DP[i] = max(DP[i],DP[j]+1)
        return max(DP[:])

特殊解法：查找

不断地去维护更新一个lis，这个list的长度就是最长递增子序列、

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 1:
            return n
        lis = []
        for i in range(len(nums)):
            if not lis:
                lis.append(nums[i])
            elif nums[i]>lis[-1]:
                lis.append(nums[i])
            elif len(lis) ==1:
                    lis[0] = nums[i]
            else:
                for j in range(len(lis)):
                    if nums[i]<= lis[j] :
                        lis[j] = nums[i]
                        break
        return len(lis)

注意这个地方nums[i]<=lis[j] 的替换

这个地方我们替换的是存在于序列中大于等于nums[i]的最小数

322.零钱兑换系列

有问题的代码：暂时还没修复。DFS暴力破解

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        self.coins = sorted(coins)
        self.min_num = -1
        n = len(coins)-1
        self.dfs(amount,n,0)
        return int(self.min_num)
        
    def dfs(self,amount,n,ans):
        if n<0:
            return False
        if amount % self.coins[n] == 0:
            ans += amount / self.coins[n]
            self.min_num=ans
            return True
        if amount < self.coins[0] :
            return False
        num = amount // self.coins[n]
        for num_coin in range(num,-1,-1):
            total = num_coin* self.coins[n]
            if(self.dfs(amount-total,n-1,ans+num_coin)):
                break
        return True

用动态规划来做：

有问题的代码：

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [0]+[10001]*amount
        dp[0] = 0 
        for coin in coins:
            for i in range(amount+1):
                dp[i] = min(dp[i],dp[i-coin]+1)
        if dp[-1] == 10001:
            return -1
        else:
            return dp[-1]

问题：dp[i-coin]：i-coin这里有可能是硬币叠加达不到的数量

修复问题：

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [0]+[10001]*amount
        dp[0] = 0 
        for coin in coins:
            for i in range(coin,amount+1):
                dp[i] = min(dp[i],dp[i-coin]+1)
        if dp[-1] == 10001:
            return -1
        else:
            return dp[-1]

• 时间复杂度：O(n * amount)
• 空间复杂度：O(amount)

学习简化if else的一种写法： 

注意

 return dp[-1] == 10001 ? -1:dp[-1] 

只能在C++里面用，python没有

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [0]+[10001]*amount
        dp[0] = 0 
        for coin in coins:
            for i in range(coin,amount+1):
                dp[i] = min(dp[i],dp[i-coin]+1)
        return dp[-1] if dp[-1] != 10001 else -1
        

可以这么简化

72：

错误代码：

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n1 = len(word1)
        n2 = len(word2)
        DP = [[0]*(n1+1)for _ in range(n2+1)]
        for i in range(n1+1):
            DP[0][i] = i
        for j in range(n2+1):
            DP[j][0] = j
        for i in range(1,n1+1):
            for j in range(1,n2+1):
                if word1[i-1] == word2[j-1]:
                    DP[i][j] = DP[i-1][j-1]
                else:
                    DP[i][j] = min(DP[i-1][j-1],DP[i-1][j],DP[i][j-1])+1
        return DP[-1][-1]

            

错误原因：DP[i][j]  是把word1[i-1] 变成word[j-1] 的字符串的最小操作次数。需要搞清楚维度

import numpy as np
DP = [[0] * (5) for _ in range(6)]
print(np.array(DP).shape)
#(6, 5)

思路理解强调：

对“dp[i-1][j-1] 表示替换操作，dp[i-1][j] 表示删除操作，dp[i][j-1] 表示插入操作。”的补充理解：

以 word1 为 "horse"，word2 为 "ros"，且 dp[5][3] 为例，即要将 word1的前 5 个字符转换为 word2的前 3 个字符，也就是将 horse 转换为 ros，因此有：

(1)替换操作： dp[i-1][j-1]，即先将 word1 的前 4 个字符 hors 转换为 word2 的前 2 个字符 ro，然后将第五个字符 word1[4]（因为下标基数以 0 开始） 由 e 替换为 s（即替换为 word2 的第三个字符，word2[2]）

(2)插入操作： dp[i][j-1]，即先将 word1 的前 5 个字符 horse 转换为 word2 的前 2 个字符 ro，然后在末尾补充一个 s

(3)删除操作： dp[i-1][j]，即先将 word1 的前 4 个字符 hors 转换为 word2 的前 3 个字符 ros，然后删除 word1 的第 5 个字符

正确代码：

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n1 = len(word1)
        n2 = len(word2)
        DP = [[0]*(n2+1)for _ in range(n1+1)]
        for i in range(n1+1):
            DP[i][0] = i
        for j in range(n2+1):
            DP[0][j] = j
        for i in range(1,n1+1):
            for j in range(1,n2+1):
                if word1[i-1] == word2[j-1]:
                    DP[i][j] = DP[i-1][j-1]
                else:
                    DP[i][j] = min(DP[i-1][j-1],DP[i-1][j],DP[i][j-1])+1
        return DP[-1][-1]

            

时间复杂度：O（(n1+1)*(n1+2)）

空间复杂度：O