动态规划题 leetcode

1. 62. 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7
输出：28

示例2:

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

解法1: 动态规划， 还是要发现其中的规律

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 隐含了 动态规划思想： dp(i, j) = dp(i-1, j) + dp(i, j-1)
        # O(mxn) O(mxn)
        dp = []
        for i in range(m):
            temp = []
            for j in range(n):
                if i == 0: # 第一行 都为1 
                    temp.append(1)
                elif j == 0: # 第一列 都为1
                    temp.append(1)
                else: # 其余先为0， 
                    temp.append(0)
            dp.append(temp)
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]  # 按照递推式 计算； 
        return dp[-1][-1]

2. LCP 19. 秋叶收藏集

小扣出去秋游，途中收集了一些红叶和黄叶，他利用这些叶子初步整理了一份秋叶收藏集 leaves， 字符串 leaves 仅包含小写字符 r 和 y， 其中字符 r 表示一片红叶，字符 y 表示一片黄叶。
出于美观整齐的考虑，小扣想要将收藏集中树叶的排列调整成「红、黄、红」三部分。每部分树叶数量可以不相等，但均需大于等于 1。每次调整操作，小扣可以将一片红叶替换成黄叶或者将一片黄叶替换成红叶。请问小扣最少需要多少次调整操作才能将秋叶收藏集调整完毕。

示例 1：

输入：leaves = "rrryyyrryyyrr"

输出：2

解释：调整两次，将中间的两片红叶替换成黄叶，得到 "rrryyyyyyyyrr"

示例2:

输入：leaves = "ryr"

输出：0

解释：已符合要求，不需要额外操作

• 3 <= leaves.length <= 10^5
• leaves 中只包含字符 'r' 和字符 'y'

解法1: 动态规划，（多看看这些题，动态规划题还是很难想到解法）

class Solution:
    def minimumOperations(self, leaves: str) -> int:
        #  最少需要多少调整， 最优问题
        # 动态规划, 即使不懂，也要会写答案
        n = len(leaves)
        dp = [[0]*n for i in range(3)]
        # dp[0][i]:  变为纯红
        # dp[1][i]: 红黄需要修改几次  
        # dp[2][i]: 红黄红需要修改几次
        for k, v in enumerate(leaves):
            if k == 0:
                dp[0][k] = int(v != 'r')  # 不为红，替换为红
            else:
                dp[0][k] = dp[0][k-1] + (v != 'r')
            if k == 0:
                dp[1][k] = dp[0][k]
            else:
                dp[1][k] = min(dp[0][k-1] + (v!='y'), dp[1][k-1]+(v!='y')) # 两种情况取最小值

            if k < 2:
                dp[2][k] = dp[1][k] # 不是 k-1
            else:
                dp[2][k] = min(dp[1][k-1] + (v!='r'), dp[2][k-1]+(v!='r')) # 两种情况
        # print(dp[0])
        # print(dp[1])
        # print(dp[2])
        return dp[2][-1]

 

本文地址：https://blog.csdn.net/qq_23944915/article/details/110939286