leetcode探索初级算法之动态规划

1. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

# 爬楼梯
# 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
# 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
# 注意：给定 n 是一个正整数。


class Solution:
    def climbStairs(self, n: int) -> int:
        nums = [0, 1, 2]
        if n == 1:
            return nums[1]
        elif n == 2:
            return nums[2]
        else:
            for i in range(3, n + 1):
                nums.append(nums[i-1] + nums[i-2])
        return nums[n]

2. 买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。

# 买卖股票的最佳时机
# 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
# 如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
# 注意：你不能在买入股票前卖出股票。


class Solution:
    def maxProfit(self, prices):
        # 存放差值
        z = []
        # 处理特殊情况
        if not prices or len(prices) == 1:
            return 0
        # 将当前值与后面最大的值做差
        for i in range(len(prices) - 1):
            z.append(max(prices[i + 1:]) - prices[i])
        # 利润大于零的情况
        if max(z) >= 0:
            return max(z)
        else:
            return 0

3.最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

# 最大子序和
# 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。


class Solution:
    def maxSubArray(self, nums) -> int:
        one_num = 0
        max_num = nums[0]
        for i in range(len(nums)):
            one_num += nums[i]
            max_num = max(max_num, one_num)
            if one_num < 0:
                one_num = 0
        return max_num

4.打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

# 打家劫舍
# 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
# 给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。


class Solution:
    def rob(self, nums) -> int:
        if len(nums) == 0:
            return 0
        if len(nums) <= 2:
            return max(nums)
        # 第一种解法
        # last, now = 0, 0
        # for i in nums:
        #     last, now = now, max(last + i, now)
        #     print(last, now)
        # return now
        # 第二种解法
        # dp初始化，除前三个，其余均设为0
        dp = [nums[0]] + [nums[1]] + [nums[0] + nums[2]] + [0] * (len(nums) - 3)
        for i in range(3, len(nums)):
            dp[i] = nums[i] + max(dp[i - 2], dp[i - 3])
        return max(dp)