【算法-面试】动态规划专题之一维dp

本文主要是介绍【算法-面试】动态规划专题之一维dp，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

# coding = "utf-8"

'''

自顶向下
    构建dp递归函数

自底向上
    构建dp数组
'''


def canJump(nums):
    '''
    给定⼀个⾮负整数数组 nums，你最初位于数组的第⼀个下标，数组中的每个元素代表你在该位置可以跳跃的
    最⼤⻓度，判断你是否能够到达最后⼀个下标
    leetcode:55. 跳跃游戏
    input:nums = [2,3,1,1,4]
    output:true
    input:nums = [3,2,1,0,4]
    output:false
    思路：
        1.贪心算法
        2.
        3.
    '''
    n = len(nums)
    farthest = 0
    for i in range(n - 1):
        farthest = max(farthest, i + nums[i])
        if farthest <= i:
            return False

    return farthest >= n - 1


def jump(nums):
    '''
    给你⼀个⾮负整数数组 nums，你最初位于数组的第⼀个位置，数组中的每个元素代表你在该位置可以跳跃的最⼤⻓度，
    请你使⽤最少的跳跃次数到达数组的最后⼀个位置（假设你总是可以到达数组的最后⼀个位置）。
    leetcode: 45. 跳跃游戏 II
    input:nums = [2,3,1,1,4]
    output:2
    思路：
        1. 贪心算法
        2.
        3.
    '''
    n = len(nums)
    jumps, farthest, end = 0, 0, 0
    for i in range(n - 1):
        farthest = max(farthest, nums[i] + i)
        if end == i:
            jumps += 1
            end = farthest
    print(jumps)
    return jumps


def canCompleteCircuit(gas, cost):
    '''
    在⼀条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。你有⼀辆油箱容量⽆限的的汽⻋，从第 i
    个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的⼀个加油站出发，开始时油箱为空。
    如果你可以绕环路⾏驶⼀周，则返回出发时加油站的编号，否则返回 -1（如果题⽬有解，该答案即为唯⼀答
    案）。
    leetcode: 134. 加油站
    input:gas = [1,2,3,4,5]
          cost = [3,4,5,1,2]
    output:3
    思路：
        1. 先通过判断总油耗和总油量的值是否小于0，如果小于0，则无解
        2. 遍历每一站的油耗和油量是否小于0，如果小于0，说明起始点需要更换为下一站
        3. 贪心算法
    '''
    n, s = len(gas), sum(gas) - sum(cost)
    if s < 0:
        return -1
    tank, start = 0, 0
    for i in range(n):
        tank += gas[i] - cost[i]
        if tank < 0:
            start += 1
            tank = 0

    # 回到0
    if start == n:
        return 0
    return start


def maxSubArray(nums):
    '''
    给定⼀个整数数组 nums，找到⼀个具有最⼤和的连续⼦数组（⼦数组最少包含⼀个元素），返回其最⼤和。
    leetcode:53. 最⼤⼦序和
    input:nums = [-2,1,-3,4,-1,2,1,-5,4]
    output:6
    思路：
        1. 以 nums[i] 为结尾的「最⼤⼦数组和」为 dp[i]
        2.
        3.
    '''
    import math
    n = len(nums)
    if n == 0:
        return 0
    dp = [0 for _ in range(n)]
    for i in range(1, n):
        dp[i] = max(nums[i], nums[i] + dp[i - 1])

    res = max(dp)
    return res


def rob(nums):
    '''
    你是⼀个专业的⼩偷，计划偷窃沿街的房屋。
    每间房内都藏有⼀定的现⾦，影响你偷窃的唯⼀制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同⼀晚上被⼩偷闯⼊，系统会⾃动报警。
    给定⼀个代表每个房屋存放⾦额的⾮负整数数组，计算你不触动警报装置的情况下，⼀夜之内能够偷窃到的最⾼⾦额。
    leetcode: 198. 打家劫舍
    input:[1,2,3,1]
    output:4
    思路：
        1.
        2.
        3.
    '''
    n = len(nums)
    if n == 0:
        return 0
    dp = [0 for _ in range(n + 2)]
    for i in range(n - 1, -1, -1):
        dp[i] = max(dp[i + 1], nums[i] + dp[i + 2])
    print(dp[0])
    return dp[0]


def rob2(nums):
    '''
    你是⼀个专业的⼩偷，计划偷窃沿街的房屋，每间房内都藏有⼀定的现⾦。
    这个地⽅所有的房屋都围成⼀圈，这意味着第⼀个房屋和最后⼀个房屋是紧挨着的。
    同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同⼀晚上被⼩偷闯⼊，系统会⾃动报警。
    leetcode:213. 打家劫舍 II
    input:[2,3,2]
    output:3
    思路：
        1. dp[i]=x  从第 i 间房子开始抢劫，最多能抢到的钱为 x
        2. base case: dp[n] = 0 从第n间房子开始，抢到0;从dp[n-1]=max(dp[n],num[n-1])=num[n-1]，即当前房间钱的数量
        3.
    '''
    n = len(nums)
    if n == 1:
        return nums[0]

    def robRange(nums, start, end, length):
        dp = [0 for _ in range(length + 1)]
        for i in range(end - 1, start - 1, -1):
            dp[i] = max(dp[i + 1], nums[i] + dp[i + 2])
        return dp[start]

    return max(
        robRange(nums, 0, n - 2, n),  # 取第一个而不取最后一个
        robRange(nums, 1, n - 1, n)  # 取第二个且取最后一个
    )


def rob3(root):
    '''
    198. 打家劫舍（简单） 和 213. 打家劫舍 II（中等） 的扩展。
    这次房屋是放在⼆叉树上，计算在不触动警报的情况下，⼩偷⼀晚能够盗取的最⾼⾦额。
    leetcode: 337. 打家劫舍 III
    input:[3,2,3,null,3,null,1]
         3
        / \
       2   3
        \   \
         3   1
    output:7
    思路：
        1.
        2.
        3.
    '''

    class Rob:
        def __init__(self):
            self.memo = dict()

        def _rob(self, _root):
            if _root is None:
                return 0
            if _root in self.memo:
                return self.memo[_root]
            # 抢
            do = _root.val
            if _root.left is not None:
                do += self._rob(_root.left.left) + self._rob(_root.left.right)
            if _root.right is not None:
                do += self._rob(_root.right.left) + self._rob(_root.right.right)

            # 不抢
            not_do = self._rob(_root.left) + self._rob(_root.right)

            res = max(do, not_do)
            self.memo[_root] = res
            return res

        def run(self, _root):
            return self._rob(_root)

    r = Rob()
    res = r.run(root)
    print(res)


def lengthOfLIS(nums):
    '''
    给你⼀个整数数组 nums，找到其中最⻓严格递增⼦序列的⻓度。
    ⼦序列是由数组派⽣⽽来的序列，例如 [3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的⼦序列。
    leetcode: 300. 最⻓递增⼦序列
    input:[10,9,2,5,3,7,101,18]
    output:4
    思路：
        1. 子序列不需要连续
        2. dp[i]代表以nums[i]这个数结尾的最长递增子序列的长度
        3.
    '''
    n = len(nums)
    if n == 0:
        return 0
    dp = [1 for _ in range(n)]
    for i in range(n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    res = max(dp)
    print(res)
    return res


def coinChange(coins, amount):
    '''
    给你⼀个整数数组 coins，表示不同⾯额的硬币；以及⼀个整数 amount，表示总⾦额。
    计算并返回可以凑成总⾦额所需的最少的硬币个数。
    如果没有任何⼀种硬币组合能组成总⾦额，返回 -1（你可以认为每种硬币的数量是⽆限的）。
    leetcode: 322. 零钱兑换
    input:coins = [1, 2, 5], amount = 11
    output:3
    思路：
        1. 自底向上:dp[i]=x，目标金额为i时，至少需要x枚硬币
        2. 自顶向下:def dp()
        3.
    '''
    dp = [amount + 1 for _ in range(amount + 1)]
    dp[0] = 0  # 金额为0时，需要0枚硬币
    for i in range(len(dp)):
        for coin in coins:
            if i - coin < 0:
                # 说明给出的coin数值大，凑不出金额i，子问题无解
                continue
            dp[i] = min(dp[i], 1 + dp[i - coin])
    if dp[amount] == amount + 1:
        return -1
    return dp[amount]


def fib(n):
    '''
    斐波那契数，通常⽤ F(n) 表示，形成的序列称为 斐波那契数列。
    该数列由 0 和 1 开始，后⾯的每⼀项数字都是前⾯两项数字的和。
    leetcode:509. 斐波那契数
    input:2
    output:1
    思路：
        1.
        2.
        3.
    '''
    dp = [1 for _ in range(n)]
    if n == 1 or n == 2:
        return 1
    for i in range(2, n):
        dp[i] = dp[i - 1] + dp[i - 2]

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


def maxEnvelops(envelops):
    '''
    给你⼀个⼆维整数数组 envelopes，其中 envelopes[i] = [wi, hi]，表示第 i 个信封的宽度和⾼度。
    当另⼀个信封的宽度和⾼度都⽐这个信封⼤的时候，这个信封就可以放进另⼀个信封⾥，如同俄罗斯套娃⼀样。
    请计算 最多能有多少个信封能组成⼀组“俄罗斯套娃”信封（即可以把⼀个信封放到另⼀个信封⾥⾯）。
    leetcode:354. 俄罗斯套娃信封问题
    input:[[5,4],[6,4],[6,7],[2,3]]
    output:3
    思路：
        1.
        2.
        3.
    '''
    n_env = len(envelops)
    sorted_envelops = sorted(envelops, key=lambda x: (x[0], -x[1]))

    def lenOfLIS(nums):
        n = len(nums)
        if n == 0:
            return 0
        dp = [1 for _ in range(n)]
        for i in range(n):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        print('max LIS: ', max(dp))
        return max(dp)

    height = [sorted_envelops[i][1] for i in range(n_env)]
    print(height)
    return lenOfLIS(height)


if __name__ == "__main__":
    # jump([2, 3, 1, 1, 4])
    # print(canJump([2, 3, 1, 1, 4]))
    # print(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
    # rob([1, 2, 3, 1])
    # rob([2, 7, 9, 3, 1])
    # print(rob2([2, 3, 2]))
    # from code_brush.base_problem.binary_tree.binary_tree import buildTreeByArray
    #
    # t = buildTreeByArray([3, 2, 3, '#', 3, '#', 1])
    # rob3(t)
    #
    # lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])
    print(coinChange([1, 2, 5], 11))
    fib(6)  # 8
    maxEnvelops([[5, 4], [6, 4], [6, 7], [2, 3]])

这篇关于【算法-面试】动态规划专题之一维dp的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！