chapter3-dynamic-algorithm

Posted on | In | | Visitors: ℃
Words count in article: 8.1k | Reading time ≈ 38

chapter3-dynamic-algorithm

参考链接

[TOC]

斐波那契数列
  1. 爬楼梯
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    import sys
    import math
    import functools
    def climbStairs(n):
        # 递归的方法就是遍历每一次方法，
        # 直接最后两步或者一部的时候计数计科。
        # 就像一颗树，每次减去1和2构成两个分支，依次类推，直到所有的叶子节点为1和2为止
        # 这就是递归，自定向上的逻辑方法
        def dg_c(n):
            if n == 1:
                return 1
            if n == 2:
                return 2
            else:
                return dg_c(n-1) + dg_c(n-2)
        print(dg_c(n))

        # 动态规划，对于每一次上台阶的次数，都是上两次方法之和
        # 比如'3'的次数是'2'和'1'的次数和就是3次。
        # 因此只需要构建前两次flag 进行记录 依次往前推，就可以计算出，最终结果
        # 这就是动态规划，自底向上的逻辑方法
        def dy_c(n):
            pre1,pre2 = 2,1
            if n <= 2:
                return n
            for i in range(2,n,1):
                cur = pre1 + pre2
                pre2 = pre1
                pre1 = cur
                print(pre1,pre2)
            print(pre1)
        dy_c(n)
    climbStairs(4)
  2. 强盗抢劫
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    def rob(nums):
        # 抢劫一排住户，但是不能抢邻近的住户，求最大抢劫量。
        # 不能够抢劫相邻的住户，意思对于i来说，如果要这个物品，我们就不能够要i-1的物品
        # 因此,代码如下，代码实现逻辑难点，在于如何记录不相邻数据之和
        def rob1(nums):
            n = len(nums)
            if n <= 2:
                if n == 0:
                    return 0
                return max(nums)
            db = [i for i in nums]
            db[1] = max(nums[0],nums[1])
            for i in range(2,n):
                db[i] = max(db[i-1], db[i-2] + nums[i])
            print(db[-1])

        #优化空间，只需要累计后前后两个数即可，由上分析可得出
        def rob2(nums):
            pre1, pre2 = 0, 0
            for i in range(len(nums)):
                cur = max(pre2+nums[i],pre1)
                pre2 = pre1
                pre1 = cur
            print(pre1)
        rob2(nums)
        rob1(nums)
    rob([8,7,9,23,1])
  3. 强盗在环形街区抢劫
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    def rob_II(nums) -> int:
        # 相比较上一题，这一题，房子的排列组成了一环，以为这第一房子和最后一个房子是相邻的。
        # 也意味着每一个位置都能够成为起点
        n = len(nums)
        if n <= 2:
            if n == 0:
                return 0
            return max(nums)
        def rob(nums, first, last):
            pre1, pre2 = 0, 0
            for i in range(first,last):
                cur = max(pre2+nums[i],pre1)
                pre2 = pre1
                pre1 = cur
            return pre1
        res = max(rob(nums,0, n-1),rob(nums,1,n))
        print(res)
        return res	
    rob_II([8,7,9,23,1])
  4. 母牛生产
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    #假设农场中成熟的母牛每年都会生 1 头小母牛，并且永远不会死。第一年有 1 只小母牛，从第二年开始，
    # 母牛开始生小母牛。每只小母牛 3 年之后成熟又可以生小母牛。给定整数 N，求 N 年后牛的数量。
    #今年的母牛=去年母牛的数量和三年前母牛的数量
    def cownum(N):
        def dg_c(N):
            if N <= 1:
                return 1
            return dg_c(N-1)+dg_c(N-3)
        print(dg_c(N))
    cownum(7)
矩阵路径
  1. 矩阵的最小路径和
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    # 求从矩阵的左上角到右下角的最小路径和，每次只能向右和向下移动。
    def minPathSum(grid) -> int:
        # 由题意可知，从矩阵的左上角到右下角的最小路径和，因此每次路径的数，与之相关的只有这个数的向上一个和左边一个，
        # 即如果这个数为grid[i][j],关联的数为grid[i-1][j] ,grid[i][j-1] 但是对于矩阵来说是有边界的，
        # 所以要解决如何遍历边界的值，也就是i和j等于0的时候
        # 由于矩阵每次关联的只有上一行的数据，所以临时存储只需要一行的列表即可
        def mps1(grid):
            db = [i for i in grid[0]]
            a = 0
            for i,v in enumerate(db):
                a += v
                db[i] = a
            for i in range(1,len(grid)):
                for j in range(len(grid[0])):
                    try:
                        db[j] = min(db[j-1],db[j]) + grid[i][j]
                    except:
                        db[j] = min(999999, db[ j ]) + grid[i][j]
            print(db[-1])

        def mps2(grid):
            m, n = len(grid), len(grid[0])
            if m == 0 or n == 0:
                return 0
            dp = [0 for i in grid[0]]
            for i in range(m):
                for j in range(n):
                    if j == 0:
                        dp[j] = dp[j]
                    elif i == 0:
                        dp[j] = dp[j-1]
                    else:
                        dp[j] = min(dp[j-1],dp[j])

                    dp[j] += grid[i][j]
            print(dp[-1])

        mps1(grid)
        mps2(grid)
    grid = [
                  [1,3,1],
                  [1,5,1],
                  [4,2,1]
                ]
    minPathSum(grid)
  2. 矩阵的总路径数
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    # 统计从矩阵左上角到右下角的路径总数，每次只能向右或者向下移动
    def uniquePaths():
        # 又题意可知，每次只能向右或者向下移动。因此
        # 对于一个矩阵来说，到位置grid[i][j],是grid[i-1][j]和grid[i][j-1]次数之和
        # 当然也要考虑边界问题，所处矩阵边界位置，也就是i和j等于0的位置，次数都被置为1
        # 由于矩阵每次关联的只有上一行的数据，所以临时存储只需要一行的列表即可
        def up1():
           m, n = 7, 3
           dp = [ 1 for i in range(n) ]
           for i in range(m):
               for j in range(n):
                   if i == 0 or j == 0:
                       dp[ j ] = 1
                   else:
                       dp[ j ] = dp[ j ] + dp[ j - 1 ]
           print(dp[ -1 ])

        def up2():
            # 组合问题
            # 机器人总共移动的次数S = m + n - 2，
            # 向下移动的次数D = m - 1，
            # 那么问题可以看成从S中取出D个位置的组合数量，这个问题的解为C(S, D)。
            m, n = 7, 3
            S = m + n - 2 #总共的移动次数
            D = m - 1 #向下的移动次数
            ret = 1
            for i in range(1,D+1) :
                ret = ret * (S - D + i) // i

            print(ret)

        up1()
        up2()
    uniquePaths()
数组区间
  1. 数组区间和
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    def  sumRange(m,n):
        # 对指定区间及进行求和
        # 对矩阵进行求累加值，然后用前后索引相减，就可以得到最终值，细节在于第一个点，和如果起点是第一个位置，如何处理
        nums = [-2, 0, 3, -5, 2, -1]
        def sr(nums):
            dp = [0]
            for i in range(1,len(nums)+1):
                dp.append(nums[i-1] + dp[i-1])
            return dp
        dp = sr(nums)
        if n > 0:
            return dp[m+1] - dp[n]
        else:
            return dp[ m ]
    sumRange(5,0)
  2. 数组中等差递增子区间的个数
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    def numberOfArithmeticSlices():
        '''
        一次遍历等差子数列，在增加数过程中，我们可以发现规律如下：
        dp[2] = 1
        [0, 1, 2]
        dp[3] = dp[2] + 1 = 2
        [0, 1, 2, 3], // [0, 1, 2] 之后加一个 3
        [1, 2, 3]     // 新的递增子区间
        dp[4] = dp[3] + 1 = 3
        [0, 1, 2, 3, 4], // [0, 1, 2, 3] 之后加一个 4
        [1, 2, 3, 4],    // [1, 2, 3] 之后加一个 4
        [2, 3, 4]        // 新的递增子区间

        :return: sum(dp)
        '''
        A = [ 0, 1, 2, 3, 4 ]
        n, dp =len(A), [0 for i in A]
        if n == 0:
            return 0
        #从2开始 防止+1是 越界
        for i in range(2,n):
            if A[i] - A[i-1] == A[i-1] - A[i-2]:
                dp[i] = dp[i-1] + 1
        print(sum(dp))
        return sum(dp)
    numberOfArithmeticSlices()
分割整数
  1. 分割整数的最大乘积
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    def integerBreak():
        n = 11
        # 如果n=10,从1->10依次进行计算，并且记录每次最大数。最终会找出规律。
        # 数字4拆成2 + 2，乘积最大，为4。
        # 数字5拆成3 + 2，乘积最大，为6。
        # 数字6拆成3 + 3，乘积最大，为9。
        # 数字7拆为3 + 4，乘积最大，为12。
        # 数字8拆为3 + 3 + 2，乘积最大，为18。
        # 数字9拆为3 + 3 + 3，乘积最大，为27。
        # 数字10拆为3 + 3 + 4，乘积最大，为36
        # 其中难点在于，像10分为3*3*4,而3*3在6中，而10包含6所以在每一次推论中，要跟新最大值。
        # 因此，代码如下：
        def ib1():
             dp = [ 1 if i == 1 else 0 for i in range(n + 1) ]
             for i in range(2, n + 1):
                 for j in range(1, i):
                     dp[ i ] = max(dp[ i ], max(j * dp[ i - j ], j * (i - j)))
             print(dp)

        #数学公式
        def ib2():
             if n > 3:
                 m, k = divmod(n, 3)
                 if k == 2:
                     return 3 ** m * 2
                 if k == 1:
                     return 3 ** (m - 1) * 4
                 if k == 0:
                     return 3 ** m
             if n == 3:
                 return 2
             if n == 2:
                 return 1

        def ib3(n):
            if n == 2 or n == 3:
                return n - 1

            res = 1
            while(n > 4):
                res *= 3
                n -= 3
            return n*res

        ib1()
        print(ib2())
        print(ib3(n))
    integerBreak()
  2. 按平方数来分割整数
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    def numSquares():
        # 通过观察每一个数的最大平方组合数列可以看出
        #遍历数 最佳平方组成方式 组成平方数个数 遍历数**0.5+1
        # 1 * 1(1的平方省略)
        # 2 1+1 2 2
        # 3 1+1+1 3 2
        # 4 2**2 1  2
        # 5 2**2+1 2 3
        # 6 2**2+1+1 3 3
        # 7 2**2+1+1+1 4 3
        # 8 2**2+2**2 2 3
        # 9 3**3 1 4
        # 1 4 9...算是临界点，
        # 对于平方数来说，最大可遍历到(遍历数**0.5+1) 也就是临界点数
        # 因此有代码 numSquare2()
        n = 38
        def genertateSquareList(n):
            squareList = []
            diff, square = 3, 1
            while( square <= n):
                squareList.append(square)
                square += diff
                diff += 2
            return squareList
        squareList = genertateSquareList(n)
        print(squareList)

        dp = [0 for i in range(n+1)]
        for i in range(1,n+1):
            mv = sys.maxsize
            for square in squareList:
                if square > i:
                    break
                mv = min(mv,dp[i - square] + 1)
            dp[i] = mv
        print(dp)
        print(dp[-1])
        return dp[-1]
    numSquares()

    #动态规划
    def numSquare2():
        n = 38
        def numSquares( n: int ) -> int:
            dp = [ i for i in range(n + 1) ]
            for i in range(2, n + 1):
                print(1,int(i ** (0.5)) + 1)
                for j in range(1, int(i ** (0.5)) + 1):
                    dp[ i ] = min(dp[ i ], dp[ i - j * j ] + 1)
            print(dp[-1])
            return dp[ -1 ]
        numSquares(n)
        
    #数学方式
    def numSquares1(n: int ) -> int:
        # 直接通过规律算出来 因为次方数只在[1,2,3,4]
        #判断是不是平方
        def isSquare( n: int ) -> bool:
            sq = int(math.sqrt(n))
            return sq * sq == n

        if isSquare(n):
            return 1

        while (n & 3) == 0:
            n >>= 2

        if (n & 7) == 7:
            return 4

        sq = int(math.sqrt(n)) + 1

        for i in range(1, sq):
            if isSquare(n - i * i):
                return 2
        return 3
    3. 分割整数构成字母字符串
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    def numDecodings():
        # 91. 解码方法
        # Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
        # 从题中可以看出 当首个数字为'0' 还有'606'是无法解码的，因为没有'0.','60','06'所组成的编码
        # 对于解码来说，顺序以及数的大小是固定(最多两位进行变换)的，由此可取去推断数字只能为1为何2为当中去组成。
        # 通过对数进行递推，可以得出：
        # 当某一位是'0'时候，只能跟前面的数字[1,2]并且这一位的组合方式和前两位一样(因为前一位的数组，必须和'0'组成在一起，就不能组成前一位的方式了)
        # 当某一位属于字母范畴是'{1,2}[1,6]',这意味的组合方式是前两位的和。
        # 当这一位数字属于[7,...]，那么这意味只能单独出现，所以也和前一位相同。
        # 因此可的代码如下：

        s = '227'
        n, cur, pre = len(s), 1, 1
        if not n or s[0] == '0':
            return 0
        for i in range(1,n):
            if s[i] == '0':
                if s[i-1] == '1' or s[i-1] == '2':
                    #因为pre要和前两位的方式相同，所以直接把pre等于cur就行 就如倒退一步
                    pre = cur
                else:
                    return 0
            else:
                if s[i-1] == '1' or (s[i-1] == '2' and s[i] <= '6'):
                    pre, cur = cur + pre, pre
                else:
                    #往前走一步，pre不变（因为前一步和本次组合相同），cur等于当前的pre（需要跟进）
                    cur = pre
        print(pre)
    numDecodings()
长递增子序列
  1. 最长递增子序列
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    def lengthOfLIS():
        #300. 最长上升子序列
        nums = [ 10, 9, 2, 5, 3, 7, 101, 18 ]
        if not nums:
            return 0
        l, tails = 0, [0 for i in nums]
        def binarySearch(tail, l, num):
            left, right = 0, l
            while(left < right):
                mid = left + (right - left) // 2
                if tail[mid] == num:
                    return mid
                elif tail[mid] > num:
                    right = mid
                else:
                    left = mid + 1
            return left

        for v in nums:
            index = binarySearch(tails, l, v)
            tails[index] = v
            print(tails)
            if index == l:
                l += 1
        print(l)
    lengthOfLIS()
  2. 一组整数对能够构成的最长链
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    def findLongestChain():
        # 对于 (a, b) 和 (c, d) ，如果 b < c(很重要)，则它们可以构成一条链。
        # 如列子：[1,2], [2,3], [3,4]]
        # 只需要遍历每一个元素后，然后保存当前最小的c1，进行分别比较，然后满足b<c1即可加1，不满足，更新c1
        # 坑点：
        # 1.leetcode列子误导，全为大于1？(其实有小于1的数)
        # 2.栗子总体趋势单调？(其实顺序不一)
        # 如果组成了长链，那么整体顺序一单挑的！！！
        # 因此，我们需要进行对元素的首元素进行排序，这样就保证，后面不会出现首元素比其前面更小，而需要更新首元素的情况。
        # 对首元素排序a，而b是不变的，整体的顺序是不会产生影响的（这一步没做，会很坑），并且保证记录了当前最小的首元素
        # 所以，这需要满足要求加1即可，代码如下：
        pairs = [ [ -10, -8 ], [ 8, 9 ], [ -5, 0 ], [ 6, 10 ], [ -6, -4 ], [ 1, 7 ], [ 9, 10 ], [ -4, 7 ] ]
        if not pairs:
            return 0
        import functools
        # 可不要cmp
        def cmp( a, b ):
            if (a[ 0 ] - b[ 0 ]) < 0:
                return -1
            if (a[ 0 ] - b[ 0 ]) == 0:
                return 0
            else:
                return 1

        pairs = sorted(pairs, key = functools.cmp_to_key(cmp))
        dp = [ 1 for i in range(len(pairs)) ]
        for i in range(1, len(pairs)):
            for j in range(i):
                if pairs[ j ][ 1 ] < pairs[ i ][ 0 ]:
                    dp[ i ] = max(dp[ i ], dp[ j ] + 1)
        print(dp)
        return max(dp)
    findLongestChain()
  3. 最长摆动子序列
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    #376. 摆动序列
    def wiggleMaxLength():
        nums = [1,17,5,10,13,15,10,5,16,8]
        # 如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。
        # 坑：1.知道序列的意思-可以不连续 2 如何去转化正负关系 3. 测试样例中 是有相同数的，如何过滤（同正正 fufu一样）
        # 直观如上列列子，如果为正为1，为服即为0 [1, 0, 1, 1, 1, 0, 0, 1, 0]，
        # 直接可以看出，我们直接遍历用只想前后两指针，记录当前不连续的值和往前移动的值，就可以求出最长摆动子序列
        if not nums:return 0
        if len(set(nums)) == 1: return 1
        if len(set(nums)) == 2: return 2
        dp= []
        for i in range(1, len(nums)):
            temp = nums[i] - nums[i-1]
            if temp < 0:
                dp.append(0)
            elif temp > 0:
                dp.append(1)
        print(dp)
        if len(set(dp)) == 1:
            return 2
        maxv, cur,cv = -sys.maxsize, 1, dp[0]
        for i in range(1,len(dp)):
            if dp[i] != cv:
                cur += 1
                cv = dp[i]
            else:
                cur = cur
        print(cur+1)
        return  cur + 1

    def wiggleMaxLength1( ) -> int:
        # 如何优化
        # 从利用两指针去记录前后书过程中，判断正负，其实不需要1和0去表示。
        # 从而优化空间速度
        nums = [ 3, 3, 3, 2, 5 ]
        if not nums:
            return 0
        up, down = 1, 1
        for i in range(1, len(nums)):
            if nums[ i ] > nums[ i - 1 ]:
                up = down + 1
            if nums[ i ] < nums[ i - 1 ]:
                down = up + 1
        print(max(up,down))
        return max(up,down)
    wiggleMaxLength()
    wiggleMaxLength1()
最长公共子序列
  1. 最长公共子序列
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    # 1143. 最长公共子序列
    def longestCommonSubsequence():
        text1 = "abcde"; text2 = "ace"
        #如果为空 直接返回、
        if text1 == text2 or text1 == "" or text2 == "":
            return text2
        #方法1
        # 给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列。
        # 最直观的想法就是，两成循环，一次遍历，如果出现相同的字符，且不是同一位置的加1(难点就在于把握不同点位置的认识)，
        # 但是为了要继承字符的连续性，就要填补不是相同的字符。这很简单直接补上上一位的数值即可(因为遍历是顺序的)
        # 然后依次逻辑，代码如下：
        def lcs1():
            dp = [ [ 0 for i in range(len(text2) + 1) ] for j in range(len(text1) + 1) ]
            print(dp)
            for i in range(1, len(text1) + 1):
                for j in range(1, len(text2) + 1):
                    if text1[ i - 1 ] == text2[ j - 1 ]:
                        dp[ i ][ j ] = dp[ i - 1 ][ j - 1 ] + 1 #必须为这点，要找以前匹配过且不是本身的值
                    else:
                        dp[ i ][ j ] = max(dp[ i - 1 ][ j ], dp[ i ][ j - 1 ])
            print(dp[ -1 ][ -1 ])
            return dp[ -1 ][ -1 ]

        # 逻辑同上， 优化空间复杂度。动态规划题做多了，一般空间都是可以优化为O(n)的
        # 因为对于其中遍历到一个字符中，关联的数组就为上一个和左一个，即数为dp[ i ][ j ]那么关联的dp[ i - 1 ][ j ]和dp[ i ][ j - 1 ]
        # 这道题有一个难点就在于，如何去找到他的p[ i - 1 ][ j - 1 ]，这个值就为算上一个值时的原始值。
        # 因此优化代码逻辑如下:
        def lcs2():
            m = len(text1);n = len(text2)
            dp = [0 for i in range(n+1)]
            for i in range(1,m+1):
                temp = 0
                for j in range(1,n+1):
                    now = dp[j]
                    if text1[i-1] == text2[j-1]:
                        dp[j] = temp + 1
                    else:
                        dp[j] = max(dp[j-1], dp[j])
                    temp = now
            print(dp[-1])
            return dp[-1]
        lcs1()
        lcs2()
    longestCommonSubsequence()
    0-1 背包
    1. 0-1 背包
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    def knapsack():
        # 有一个容量为 N 的背包，要用这个背包装下物品的价值最大，这些物品有两个属性：体积 w 和价值 v。
        # 确定值-背包重量一定即w 通过w去确定背包所能装载的最大值v
        # 给定物品重量与价值列表如下wb->vb
        # 通过去遍历wb，意为每次增加一个物品
        # 二层遍历背包容量W，判断背包是否能够装载当前物品。（并且要参考以前获得的值）
        # 如果装载不下当前物品，就填充上一次的价值
        # 即代码逻辑如下：
        wb = [2, 4]
        vb = [3, 11]
        N, W = 2, 8
        def ks1():
            wv = [ [ 0 for j in range(W + 1) ] for i in range(N + 1) ]
            for i in range(1, N + 1):
                w, v = wb[ i - 1 ], vb[ i - 1 ]
                for j in range(1, W + 1):
                    if j >= w:
                        wv[ i ][ j ] = max(wv[ i - 1 ][ j ], wv[ i ][ j - w ] + v)
                    else:
                        wv[ i ][ j ] = wv[ i - 1 ][ j ]
            print(wv[ -1 ][ -1 ])
            return wv[ -1 ][ -1 ]

        def ks2():
            # 从上述分析可知：
            # 对于临时表wv而言，只用到了前一层的值，所以只需要O(N)的空间复杂度即可：
            # 代码如下：
            dp = [0 for i in range(W+1)]
            for i in range(1, N+1):
                w = wb[i-1]; v = vb[i-1];old = dp[1]
                for j in range(1, W+1):
                    if j >= w:
                        temp = dp[j-w] + v
                        dp[j] = max(old, temp)
                    else:
                        dp[j] = old
                    if j < W:
                        old = dp[j+1]
            print(dp[-1])

            #有上述思路，如果倒叙遍历... 会咋样呢？
            for i in range(2, N + 1):
                w = wb[ i - 1 ]
                v = vb[ i - 1 ]
                for j in range(W,0,-1):
                    if j >= w:
                        dp[ j ] = max(dp[j], dp[ j - w ] + v)
                print(dp)
            print(dp[ -1 ])
        ks1()
        ks2()
    knapsack()
  2. 划分数组为和相等的两部分
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    #416. 分割等和子集
    #题目描述给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
    def canPartition():
        nums = [1,1,1,3,5,3]
        # 由题意数组分割成两个子集，使得两个子集的元素和相等
        # 因为只包含正整数的非空数组，所以如果全部和为奇数是不可能分割的，长度小于1也不行。这就意味着我们只需要找到他均值就行
        # 因此，我们只需要遍历所给元素，因为不可重复使用，直接遍历就行
        # 如果找到其中元素为遍历均值数组v相等，即这个数可以求和找到
        # 当遍历大于v是,只需依次去判断以前的值是否可以找到即可
        # 难点在于如何判断以前的值。倒序遍历就不用考虑原始值是否被覆盖了，就比如值为10前去5等于5，就会重复使用原始值
        def cp1():
            mid = sum(nums)//2
            if sum(nums) % 2 != 0 or len(nums) <= 1:
                return False
            dp = [0 for i in range(mid+1)]
            for i, v in enumerate(nums):
                for j in range(mid,v-1,-1):
                    if dp[j-v] == 1 or v == j :
                        dp[j] = 1
                    print(v,j)
                    print(dp)
            return dp[-1]

        def cp2():
            div, remain = divmod(sum(nums), 2)
            if remain != 0:
                return False
            N = len(nums)
            nums.sort(reverse = True)

            def _dfs( target, pos ):
                if target == 0:
                    return True
                if pos < N and target < nums[ pos ]:
                    return False
                for i in range(pos, N):
                    if _dfs(target - nums[ i ], i + 1):
                        return True
                return False

            return _dfs(div, 0)
    canPartition()
  3. 改变一组数的正负号使得它们的和为一给定数
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    # 494. 目标和
    def findTargetSumWays():
        nums ,S = [ 1, 1, 1, 1, 1 ], 3

        # 改变一组数的正负号使得它们的和为一给定数
        # 又题意可知，是有正负组成两类符号组成
        # 可以将这组数看成两部分，P和N，其中P使用正号，N使用负号，有以下推导：
        # 既可以推论：
        # sum(P) - sum(N) = target
        # sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)
        # 2 * sum(P) = target + sum(nums)
        # 因此只要找到一个子集，令它们都取正号，并且和等于(target + sum(nums)) / 2，就证明存在解。

        def dy(num, S):
            div, remain = divmod(sum(nums), 2)
            if remain == 0:
                return 0

            dp = [1 if i == 1 else 0 for i in range(div + 1)]
            for i in nums:
                for j in range(div,i-1,-1):
                    if dp[j - i] == 1:
                        dp[j] += dp[j - i]

            return dp[-1]
        # 深度搜索，即遍历每一种选择
        # 就如同比遍历每一个数，然后每一个有两种选择，如同一颗树，每次长两次枝丫，知道分为列子长度数为支点。
        # 知道遍历为止 代码逻辑如下
        def dfs(nums, pos, res = 0, c=0):
            if pos > len(nums) - 1:
                if res == S:
                    return 1
                return 0
            return  dfs(nums, pos + 1, res-nums[pos], c) + dfs(nums, pos + 1, res+nums[pos], c)
        print(dfs(nums, 0, 0,0))
        print(dy(nums, S))
    indTargetSumWays()
  4. 01 字符构成最多的字符串
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    def findMaxForm():
        import functools
        strs = ["111","1000","1000","1000"];m = 9; n = 3

        # 1. 如果用长度去排序，然后用贪婪算法，贪婪算法错误
        # 2. 如果用每一个元素统计1和0的个数，然后排序就正确比动态规划时间复杂度更低O(n*lg(n))
        # 所以要找好指标，就像如果背包用比列系数也挺不错 哈哈哈
        def tl():
            def tl1():
                def cmp( a, b ):
                    if (len(a) - len(b)) < 0:
                        return -1
                    if (len(a) - len(b)) == 0:
                        return 0
                    else:
                        return 1
                pairs = sorted(strs, key = functools.cmp_to_key(cmp))
                print(pairs)
                c0,c1 = 0, 0
                m0, n0 = 0, 0
                for str in pairs:
                    for s in str:
                        if s == '0':
                            m0 += 1
                        else:
                            n0 += 1
                    if m >= m0 and  n >= n0:
                        c0 += 1
                print(c0)
                return c0
            def tl2():
                def getMax( counts, m: int, n: int ) -> int:
                    ans = 0
                    for k in counts:
                        if m >= k[ 0 ] and n >= k[ 1 ]:
                            ans += 1
                            m -= k[ 0 ]
                            n -= k[ 1 ]
                    return ans

                counts = [ ]
                from collections import Counter
                for s in strs:
                    d = Counter(s)
                    counts.append([ d[ '0' ], d[ '1' ] ])
                c1 = sorted(counts, key = lambda x:min(x[ 0 ], x[ 1 ]))
                c2 = sorted(counts, key = lambda x:min(m - x[ 0 ], n - x[ 1 ]), reverse = True)
                return max(getMax(c1, m, n), getMax(c2, m, n))

        def dy():
            # 类比于0-1背包问题，知识把建表中，求上一次元素的思路，化为当前01的个数，这就是由于不是而
            # 求上一值的过程 就是验证此值是否能够填入
            dp = [ [0 for j in range(n+1)] for i in range(m+1)]
            for str in strs:
                ones, zeros = 0, 0
                for s in str:
                    if s == '0':
                        zeros += 1
                    else:
                        ones += 1

                for i in range(m, zeros-1, -1):
                    for j in range(n, ones-1, -1):
                        dp[i][j] = max(dp[i][j], dp[i-zeros][j-ones] + 1)

            print(dp[-1][-1])
            return dp[-1][-1]
        tl()
        dy()	
    findMaxForm()
  5. 找零钱的最少硬币数
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    def coinChange():
        coins = [186,419,83,408]; amount = 6249

        # 同背包问题即可，对价格进行依次遍历，保证不重复使用
        # 然后对目标价格遍历，保证累加性（每种结果能够遍历），判断使得每次取出最佳分数
        # 代码如下：
        if amount == 0:
            return 0
        def dy():
            dp = [ sys.maxsize for i in range(amount + 1) ]

            for c in coins:
                for i in range(c, amount + 1):
                    if c == i:
                        dp[ i ] = 1
                    dp[ i ] = min(dp[ i ], dp[ i - c ] + 1)
            print(dp[ -1 ])
            if dp[ -1 ] == sys.maxsize:
                return -1
            return dp[ -1 ]
        dy()

        # 深度搜索与剪枝优化
        # 难点在于 不是一个数能够除尽的，比如amount=19，coins=[2,3],其中19对每一个数都不能被除尽，而19=15+4
        # 是能够找到零钱的。
        # 当使用深度搜索是，逻辑不能够被此干扰，而直接取余，造成没有结果。
        # 逻辑其实和动态回归一样，只是里面的一层循环进行优化和剪枝。
        minv = sys.maxsize
        coins = sorted(coins,reverse = True)
        lc, minv = len(coins), amount + 1
        dp = []
        def dfs(target, index, count):
            nonlocal minv,dp
            if count + target//coins[index] >= minv:
                return

            if target % coins[index] == 0:
                minv = count + target//coins[index]
                dp.append(coins[ index ])
                print(dp)

            if index == lc - 1:
                return
            print(index, target,coins[index],target//coins[index])
            for i in range(target//coins[index],-1,-1):
                dp.append(coins[index])
                dfs(target - coins[index]*i, index+1, count + i)
                dp = []
        dfs(amount, 0, 0)
        print(minv)
        return  -1 if minv > amount else minv
    coinChange()
  6. 找零钱的硬币数组合
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    def change():
        # 找零钱的最少硬币数思路一样，也是一个类似背包问题，只是进行求和
        amount = 5;coins = [ 1, 2, 5 ]
        # if amount == 0 :
        #     return 1
        # dp = [0 for i in range(amount + 1)]
        # for c in coins:
        #     if c > amount:
        #         continue
        #     for i in range(c,amount+1):
        #         if i == c:
        #             dp[i] += 1
        #         dp[i] += dp[i-c]
        # return dp[-1]
        if amount == 0:
            return 1
        dp = [ 1 if i == 0 else 0 for i in range(amount + 1) ]
        for c in coins:
            if c > amount:
                continue
            for i in range(-c + amount + 1):
                if dp[ i ]:
                    dp[ i + c ] += dp[ i ]
            print(dp)
        print(dp[ -1 ])
        return dp[ -1 ]
    change()
  7. 字符串按单词列表分割
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    def wordBreak():
        s = "leetcode"; wordDict = [ "leet", "code" ]

        # 由题意得，分词后顺序是变的，也就是wordDict能组成的词语只能从左到右
        # 更具所给s的长度建立矩阵
        # 矩阵然后遍历所给词典，这就保证所组成的词语是按照上诉顺序的
        # 然后难点就在于，只要出现了所给词语，就标记即可。
        dp = [0  for i in range(len(s)+1)]
        print(s[0:len(s)])
        tc, dp[0] = 0, 1
        for i in range(1,len(s) + 1):
            for w in wordDict:
                l = len(w)
                if l <= i and (w == s[i-l:i]):
                    dp[i] = (dp[i] | dp[i-l])
        print(dp[-1])
        return dp[-1]
    wordBreak()
  8. 组合总和
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    def combinationSum4():
        nums = [ 1, 2, 3 ]
        target = 4
        # 又题意可知，可以重复使用nums并且顺序不同，亦是一种结果
        # 因此代码逻辑如下：
        if not nums or target == 0:
            return 0
        def dy():
            dp = [0 for i in range(target+1)]
            # 保留nums的顺序
            # for n in nums:
            #     for i in range(target-n+1):
            #         if dp[i]:
            #             dp[i+n] += dp[i]

            #不保证nums的顺序
            for i in range(1,target+1):
                for n in nums:
                    if n > i:
                        continue
                    if n == i:
                        dp[i] += 1
                    dp[i] = dp[i] + dp[i-n]

            print(dp[-1])
            return dp[-1]
        def dfs():
            size = len(nums)
            memmory = {}

            def helper( target ):
                if target == 0:
                    return 1
                res = 0
                for i in range(size):
                    if nums[ i ] > target:
                        continue
                    next_target = target - nums[ i ]
                    if next_target in memmory:
                        res += memmory[ next_target ]
                    else:
                        memmory[ next_target ] = helper(next_target)
                        res += memmory[ next_target ]
                return res
            return helper(target)

        dy()
        dfs()
    combinationSum4()
股票交易
  1. 需要冷却期的股票交易
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    import numpy as np
    def maxProfit():
        print(6&1)
        print(float('-inf')) #infinity
        # 根据题意，每一个数都有0：买入，1：卖出，2：冷冻期。三个状态之间进行转化
        # 即如果当前i=1时，就是第一只股票，前面没有买即可初始化i=0状态为[0,0,0]
        # 这样根据状态转移方程：
        # 1.当前买入(利润) = max(上一次买入,上一次卖出 + 当前价格)->max(买入状态，卖出状态转为买入状态)->其中卖出后一直不买，期间属于冷冻期
        # 2.当前卖出(利润) = max(上一次卖出，冷冻期 - 当前价格)->max(卖出状态，买入状态转为卖出状态)->其中如果买入一次后如果一直不卖，期间属于冷冻期
        # 3.冷冻期 = 当前买入(利润)
        # 为了保证每一次循环，能够保证利益最大，所以需要取得买入和卖出当前的最大值
        # 因此代码逻辑如下：
        prices = [1,2,3,0,2]
        #如果一上述状态转换方程，根据prices退出结果为
        '''
        [[ 0. -1.  0.]#初始值解释 0：刚开始没有卖出，利润为0,1：买入一只股票利润-prices[0],3:冷冻期是上一次没有股票，所以利润0
         [ 1. -1.  0.]
         [ 2. -1.  1.]
         [ 2.  1.  2.]
         [ 3.  1.  2.]]
        '''

        if len(prices) < 2:
            return 0

        def mp1():
            n = len(prices)
            dp = np.zeros((n,3))
            dp[0][1] = -prices[0]
            for i in range(1, n):
                dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
                dp[i][1] = max(dp[i-1][1], dp[i-1][2] - prices[i])
                dp[i][2] = dp[i-1][0]
            print(max(dp[n-1][0],dp[n-1][2]))
            print(dp)
            return max(dp[n-1][0],dp[n-1][2])

        # 又上诉逻辑以及代码实现上，观察可知：
        # 保留状态0、1、2上股票之间的联系，只是当前股票和上一只股票之间进行联系
        # 因此只需要两个变量进行存储历史变量，进行转换即可
        # 代码如下：
        def mp2():
            hold, sell, freeze = -sys.maxsize, 0, 0
            for v in prices:
                hold = max(hold, sell - v)
                sell = freeze
                freeze = max(freeze, hold + v)

            print(max(sell, freeze))
            return max(sell, freeze)

        mp1()
        mp2()
    maxProfit()
  2. 需要交易费用的股票交易
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    #714. 买卖股票的最佳时机含手续费
    def maxProfit1():
        prices = [1, 3, 2, 8, 4, 9];fee = 2

        if len(prices) < 2:
            return 0
        # 股票交易有三给状态，卖出(sell):卖出是这种状态,持有(hold):买入这种状态,停歇(rest):1.卖出股票但不买入股票期间;2.买入股票但不卖出期间
        # 股票交易就在这三种状态之间进行转换即:hold->(rest)->sell->(rest)-hold(括号表示可有可无)
        # 根据这三种状态，我们就可以根据题意算出结果
        # 其中我们需要保存当前最大值，来求解最大利润。
        # 每一个状态用当前利润进行表示
        sell, hold, rest = 0, -sys.maxsize, 0
        for p in prices:
            hold = max(hold, sell - p)
            rest = hold #可以不要，只是有这种状态
            sell = max(sell,rest + p -fee )

        print(sell,rest)
        return  max(sell, rest)
    maxProfit1()
  3. 只能进行两次的股票交易
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    # 123. 买卖股票的最佳时机 III
    def maxProfit2():
        prices = [3,2,6,5,0,3]
        if len(prices) < 2:
            return 0

        firstHold, firstSell = float('-inf'), 0
        secondHold, secondSell = float('-inf'), 0
        # for p in prices:
        #     if(firstHold < -p):
        #         firstHold = -p
        #
        #     if firstSell < firstHold + p:
        #         firstSell = firstHold + p
        #
        #     if secondHold < firstSell - p:
        #         secondHold = firstSell - p
        #
        #     if secondSell < secondHold + p:
        #         secondSell = secondHold + p
        for p in prices:
            firstHold = max(firstHold, -p)
            firstSell = max(firstSell, firstHold + p)
            secondHold = max(secondHold, firstSell - p)
            secondSell = max(secondSell, secondHold + p)
        print(secondSell)

        return secondSell
    maxProfit2()
  4. 只能进行 k 次的股票交易
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    def maxProfit4():
        prices = [3,2,6,5,0,3]; k = 2

        #当交易次数，能够遍历完全部的股票的时候，只需要把利润为正的交易加和即可
        maxv = 0
        if len(prices) // 2 <= k:
            for i in range(1, len(prices)):
                if prices[i] > prices[i-1]:
                    maxv += (prices[i] - prices[i-1])
            return maxv
        elif len(prices) < 2 or k == 0:
            return 0

        # 当交易次数k，不能够遍历所以股票时
        # 说明有些股票将会被省去，但是股票的相对顺序是不可变的
        # 因此可你存储矩阵dp[i][j]如下，其中i表示k次交易，j->(0:买入(hold)，1:卖出(sell))
        dp = [[float('-inf'),float('-inf')] for i in range(k)]
        for p in prices:
            dp[0][0] = max(dp[0][0], -p)
            dp[0][1] = max(dp[0][1], dp[0][0] + p)
            for i in range(1,k):
                dp[i][0] = max(dp[i][0], dp[i - 1][1] - p)
                dp[i][1] = max(dp[i][1], dp[i][0] + p)

        print(dp[-1][1])
        return dp[-1][1]
    maxProfit4()
字符串编辑
  1. 删除两个字符串的字符使它们相等
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    def minDistance():
        word1, word2 = "ab", "a"
        l1, l2 = len(word1), len(word2)
        # 又题意可知，最少删除字符，使他们相等，也就是保留他们最常相等的字符串
        # 因此求出他们公有最长公共子序列就行
        # 代码如下：
        dp = [[0 for i in range(l2+1)] for j in range(l1+1)]
        for i in range(1,l1+1):
            for j in range(1,l2+1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
        print(dp[-1][-1])
        return l1+l2-2*dp[-1][-1]
    minDistance()
  2. 编辑距离
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    def  minDistance1():
        word1, word2 = "horse", "ros"
        # 如过把word2看作子序列，意思先在word1中找到最长的公共子序列(意味着相同的不加1)，而其他的就需要通过增加，替换操作进行配对
        # 就如同做字符串编辑的思路
        # 只是多考虑了相等的地方如何去处理
        # 只是多考虑了相等的地方如何去处理
        l1, l2 = len(word1), len(word2)
        if not l1 and not l2:
            return 0
        if not l1 or not l2:
            return 1

        dp = [ [i if j == 0 else 0 for i  in range(l2 + 1) ] for j in range(l1 + 1) ]
        for i in range(l1 + 1):
            dp[i][0] = i
        print(dp)
        for i in range(1, l1 + 1):
            for j in range(1, l2 + 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 ], min(dp[ i ][ j - 1 ], dp[ i - 1 ][ j ]))+1
        print(dp[ -1 ][ -1 ])
        return dp[ -1 ][ -1 ]
    minDistance1()
  3. 复制粘贴字符
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    #650. 只有两个键的键盘
    def minSteps():
        n = 3
        def dg(n):
            if n == 1:
                return 0
            for i in range(2, int(math.sqrt(n) + 1)):
                if n % i == 0:
                    return i + dg(n/i)
            return n
        print(dg(n))

        def dy(n):
            dp = [0 for i in range(n+1)]
            h = int(math.sqrt(n))
            for i in range(2,n+1):
                dp[i] = i
                for j in range(2, h+1):
                    if i % j == 0:
                        dp[i] = dp[j] + dp[i//j]
                        break

            print(dp[-1])
            return  (dp[-1])

        dy(n)

        def fj(n) -> int:
            # 质数分解,比如输入为70时,70 = 2×5×7
            # 操作次数为:2+5+7
            res = []
            while n > 1:
                tmp = 2
                while n % tmp:
                    tmp += 1
                n//=tmp
                res.append(tmp)
            return sum(res)

        fj(n)
     minSteps()