动态规划优化刷题

714. 买卖股票的最佳时机含手续费

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        n = len(prices)
        dp = [[0] * 2 for _ in range(n)]
        dp[0][0] = 0
        dp[0][1] = -prices[0]
        for i in range(1, n):
            idx = i % 2
            pre_idx = 1 - idx
            dp[idx][0] = max(dp[pre_idx][1] + prices[i] - fee, dp[pre_idx][0])
            dp[idx][1] = max(dp[pre_idx][1], dp[pre_idx][0] - prices[i])
        return max(dp[(n-1) % 2])

213. 打家劫舍 II

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1: return nums[0]
        dp = [[0]  * 2  for _ in range(2)]
        dp[0][1] = nums[0]
        for i in range(1, n):
            idx = i % 2
            pre_idx = 1 - idx
            dp[idx][0] = max(dp[pre_idx][1], dp[pre_idx][0])
            dp[idx][1] = dp[pre_idx][0] + nums[i]
        ans1 = dp[( n-1) % 2][0]
        dp[0][1] = 0
        dp[0][0] = 0
        for i in range(1, n):
            idx = i % 2
            pre_idx = 1 - idx
            dp[idx][0] = max(dp[pre_idx][1], dp[pre_idx][0])
            dp[idx][1] = dp[pre_idx][0] + nums[i]
        ans2 = max(dp[( n - 1) % 2])
        return max(ans1 ,ans2)

416. 分割等和子集

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        sum_val = sum(nums)
        if sum_val % 2: return False 
        n = len(nums)
        f = [False] * (sum_val + 1)
        f[0] = True
        tmp  = 0
        for num in nums:
            tmp += num
            for j in range(tmp, num - 1, -1):
                f[j] |= f[j - num]
        return f[sum_val // 2]
        

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        sum_val = sum(nums)
        if sum_val % 2: return False 
        n = len(nums)
        f = [[False] * (sum_val + 1) for _ in range(2)]
        f[0][0] = True 
        for  i in range(1, n):
            idx  = i  % 2
            pre_idx  =  1 - idx
            for j in range(sum_val + 1):
                f[idx][j] = f[pre_idx][j] or f[pre_idx][j - nums[i]]
        return f[(n-1) % 2][sum_val // 2]

474. 一和零

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        length = len(strs)
        dp = [[[0] * (n + 1) for _ in range(m + 1)] for _ in range(length + 1)]
        for k in range(1, length + 1):
            counter = collections.Counter(strs[k - 1])
            for i in range(m + 1):
                for j in range(n + 1):
                    dp[k][i][j] = dp[k - 1][i][j]
                    if i < counter['0'] or j < counter['1']: continue
                    dp[k][i][j] = max(dp[k][i][j], dp[k - 1][i - counter['0']][j - counter['1']]  + 1)
        return dp[length][m][n]

494. 目标和

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        sum_val = sum(nums)
        if target >sum_val: return 0
        n = len(nums)
        if n == 1:return 1 if abs(nums[0]) == abs(target) else 0
        basis = sum_val
        dp = [[0] * (2 * sum_val + 1) for _ in range(2)]
        dp[0][0 + basis] = 1
        for i in range(0, n):
            idx = i % 2
            next_idx  =  1 - idx
            for j in range(0, 2 * sum_val + 1):
                if j + nums[i] < 2 * sum_val + 1:
                    dp[next_idx][j + nums[i]] += dp[idx][j]
                if j - nums[i] >=0:
                    dp[next_idx][j - nums[i]] += dp[idx][j]
            dp[idx] = [0] * (2 * sum_val + 1)
        return dp[n % 2][basis + target]

322. 零钱兑换

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

518. 零钱兑换 II

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        f = [0] * (amount + 1)
        f[0] = 1
        for x in coins:
            for j in range(x, amount + 1):
                f[j] += f[j - x]
        return f[amount] 

377. 组合总和 Ⅳ

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        f = [0] * (target + 1)
        f[0] = 1
        for i in range(1, target + 1):
            for num in nums:
                if i < num: continue
                f[i] += f[i - num]
        return f[target]

382. 链表随机节点

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:

    def __init__(self, head: Optional[ListNode]):
        self.head = head

    def getRandom(self) -> int:
        node = self.head 
        count = 1
        ans = 0
        while node:
            if random.randint(1, count) == count:
                ans = node.val
            count += 1
            node = node.next
        return ans 


# Your Solution object will be instantiated and called as such:
# obj = Solution(head)
# param_1 = obj.getRandom()

462. 最少移动次数使数组元素相等 II

class Solution:
    def minMoves2(self, nums: List[int]) -> int:
        flag = 1
        if len(nums) % 2 != 0:
            flag = 2
            nums = nums[:] + nums[:]
        nums.sort()
        ans1 = sum(nums[: len(nums) // 2])
        ans2 = sum(nums[len(nums) // 2: ])
        return (ans2 - ans1) // flag

77. 组合

class Solution:
    def dfs(self, n, m, k, buff):
        if k == 0:
            self.ans.append(buff)
            return 
        for i in range(m, n + 1):
            self.dfs(n, i + 1, k - 1, buff+[i])
    def combine(self, n: int, k: int) -> List[List[int]]:
        self.ans = []
        self.dfs(n, 1, k, [])
        return self.ans 

234. 回文链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverse(self, head):
        newhead = ListNode(None)
        cur = head
        while cur:
            tmp = cur.next
            cur.next = newhead.next
            newhead.next = cur 
            cur = tmp
        return newhead.next
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:
            return True 
        slow = head
        fast = head
        while fast and fast.next:
            fast = fast.next
            if not fast.next:
                break
            fast = fast.next
            slow = slow.next
        newhead = self.reverse(slow.next)
        slow.next = None
        p, q = head, newhead
        while p and q:
            if p.val != q.val: return False 
            p = p.next
            q = q.next
        return True