python - leetcode 2键键盘问题的递归方法
问题描述
我正在尝试 使用递归解决此问题https://leetcode.com/problems/2-keys-keyboard/ 。我初始化了 2 个变量屏幕和缓冲区。screen 表示屏幕上所有字符的计数,buffer 表示上一步复制的所有字符的计数
所以我们复制的时候函数是这样调用的 - function(screen,screen)
和粘贴意味着 - 功能(屏幕+缓冲区,缓冲区)
但这不起作用这是代码-
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))
解决方案
两个问题:
- 需要限制移动次数(即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
添加记忆
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
推荐阅读
- python - 使用 Conv2DTranspose 输出其输入形状的双倍
- flutter - 如何理解颤动中的蓝牙特性(循环速度和节奏)数据?
- css - React js下拉菜单不可滚动
- powershell - 如何使用powershell脚本在文本文件的行首和行尾添加特殊字符?
- python - Python csv.DictReader 返回 KeyError
- django - Django,如何在 forms.ModelForm 中设置值
- python - 模型放置
- oop - 状态设计模式 - 当一个新状态添加到父状态时,这会导致另一个状态也发生变化,我们如何防止改变另一个状态
- sql - 如何在 SQL 中查找频率
- email - 电子邮件液体模板 - 拆分字符串并显示字符串 [index] 内联