leetcode 2键键盘问题的递归方法

Question

我正在努力解决这个问题https://leetcode.com/problems/2-keys-keyboard/使用递归。我初始化了2个变量屏幕和缓冲区。screen表示屏幕上所有字符的计数，buffer表示在前一步骤上复制的所有字符的数量

所以当我们复制时，函数是这样调用的-功能(屏幕，屏幕)

粘贴意味着-功能(屏幕+缓冲区、缓冲区)

但这不起作用这是代码-

def keyboard(screen,buffer, c,n):
if screen == n:
return c
if screen>n:
return
if buffer>n:
return    


keyboard(screen+buffer,buffer,c+1,n)
keyboard(screen,screen,c+1,n)
print(keyboard(1,0,0,8)) 

我正在获得最大递归深度这是记忆方法

def keyboard(self,screen,buffer,c,n,dp):

large_num = 100000 # larger than possible moves

if dp[screen][buffer] != -1:
return dp[screen][buffer]

if screen == n:
return c           
if screen>n:
return large_num  
if buffer>n:
return large_num  
if c > n:  
return large_num

dp[screen][buffer] =  min(self.keyboard(screen,screen,c+1,n,dp), self.keyboard(screen+buffer,buffer,c+1,n,dp))
return dp[screen][buffer]  
def minSteps(self, n: int) -> int:
dp = [[-1 for i in range(n+1)] for j in range(n+1)]
return(self.keyboard(1,0,0,n,dp))

Answer 1

两个问题：

• 需要限制移动次数(即c值)
• 需要通过最小化来优化动作

代码

def keyboard(screen,buffer,c,n):
large_num = 100000 # larger than possible moves
if screen == n:
return c           # Found solution
if screen>n:
return large_num  # Out of bounds (make moves larger than max possible)
if buffer>n:
return large_num  # Out of bounds (make moves larger than max possible)
if c > n:  # limit number of moves
return large_num

# Optimize choice by taking minimum
return min(keyboard(screen,screen,c+1,n), keyboard(screen+buffer,buffer,c+1,n))
print(keyboard(1,0,0,8)) 
# Output: 6

添加Memoization

def keyboard(screen,buffer,c,n, memcache = None):
if memcache is None:
memcache = {}
large_num = 100000 # larger than possible moves
# Input state as tuple
state = (screen, buffer, c, n)
if state in memcache:
return memcache[state]
if screen == n:
return c           # Found solution
if screen>n:
return large_num  # Out of bounds (make moves larger than max possible)
if buffer>n:
return large_num  # Out of bounds (make moves larger than max possible)
if c > n:  # limit number of moves
return large_num

# Using memoization to cache current value
# Optimize choice by taking minimum
memcache[state] = min(keyboard(screen,screen,c+1,n), keyboard(screen+buffer,buffer,c+1,n))
return memcache[state]
print(keyboard(1,0,0,8)) 

使用装饰器记忆

这与前面的情况相当，但使用了一个装饰器来允许记住任何具有可清洗位置参数的函数，

def memoize(f):
"""This automates the previous example where we added a cache.  
It uses a decorator function to add a cache to any function with
hashable position arguments
"""
memo = {}
def helper(*args):
if args not in memo:            
memo[args] = f(*args)
return memo[args]
return helper
@memoize
def keyboard(screen,buffer,c,n):
large_num = 100000 # larger than possible moves
if screen == n:
return c           # Found solution
if screen>n:
return large_num  # Out of bounds (make moves larger than max possible)
if buffer>n:
return large_num  # Out of bounds (make moves larger than max possible)
if c > n:  # limit number of moves
return large_num

# Using memoization to cache current value
# Optimize choice by taking minimum
return min(keyboard(screen,screen,c+1,n), keyboard(screen+buffer,buffer,c+1,n))
print(keyboard(1,0,0,8))

修复海报备忘录代码

问题是记忆并没有超过输入的完整状态。

• 发布的代码使用(屏幕、缓冲区)作为状态
• 状态实际上是(screen，buffer，c)(不需要n，因为它是固定的)

固定代码

class Solver:
def keyboard(self,screen,buffer,c,n,dp):

large_num = n + 1 # larger than largest possible moves

if screen>n or buffer>n or c > n:
return large_num 
if dp[screen][buffer][c] != -1:
return dp[screen][buffer][c]
if screen == n:
dp[screen][buffer][c] = c          

elif buffer == 0:
dp[screen][buffer][c] = self.keyboard(screen, screen, c+1, n, dp)
else:
# screen can not be zero
# minimum of copy and paste move
dp[screen][buffer][c] =  min(self.keyboard(screen,screen,c+1,n,dp), self.keyboard(screen+buffer,buffer,c+1,n,dp))

return dp[screen][buffer][c]  
def minSteps(self, n: int) -> int:
dp = [[[-1 for i in range(n+1)] for j in range(n+1)] for k in range(n+1)]
return self.keyboard(1,0,0,n,dp)
s = Solver()
print(s.minSteps(8))
# Output: 6