leetcode：650. 只有两个键的键盘【二维dp】

题目截图

题目分析

• 当前假设有n个A，那么它一定是由m个A变过来的
• 它要么继承了m个A上一次的复制个数，要么直接复制m个A
• 注意如果继承m个A上一次的个数只需要额外一次操作，直接复制m个A需要两次
• 因此我们需要记录当前A的个数，以及上一次复制的个数
• 一般地，dp[i][j]表示当前i个A且上次复制了j个的最少次数
• 一定会有i > j
• 上一次的个数为i - j
• if i - j > j,必定沿用：dp[i][j] = min(dp[i][j], dp[i - j][j] + 1)
• if i - j == j, 必定直接复制: dp[i][j] = min(dp[i][j], min(dp[i - j]) + 2)
• 特别地，直接复制里面需要选一个dp[i - j]最小的作为更新
• 初始值dp[1][0] = 0，dp[2][1] = 2

ac code

class Solution:
    def minSteps(self, n: int) -> int:
        # dp[i][j]表示i个A的且上次复制了j个的最少次数
        # dp[i][j] = min(dp[i][j], dp[i - j][j])
        dp = [[inf] * (n + 1) for _ in range(n + 1)]
        if n == 1: return 0
        if n == 2: return 2
        dp[1][0] = 0
        dp[2][1] = 2
        for i in range(3, n + 1):
            for j in range(1, i):
                if i - j > j:
                    dp[i][j] = min(dp[i][j], dp[i - j][j] + 1)
                elif i - j == j:
                    dp[i][j] = min(dp[i][j], min(dp[i - j]) + 2)
        #print(dp)
        return min(dp[-1])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

总结

• 看看当前状态怎么转移的
• 要么沿用要么更新
• 需要每个沿用之前的花费，因此要二维
• 更新需要找到最小的贪心处理