数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学检查N能否表示为从集合{A, B}中选择的整数之和（Python）
假设我们有一个目标数字。我们还有另外两个数字A和B。我们必须检查是否可以通过任意多次添加A和B来获得目标数字。
因此，如果输入像目标 = 26，A = 5，B = 7，则输出为True，因为我们可以通过添加A和B来获得26，例如 (7 + 7 + 7 + 5)。
为了解决这个问题，我们将遵循以下步骤：
- 定义一个函数util()。这将接收x、a、b、is_ok和target。
- 如果x > target，则
- 返回。
- 如果is_ok[x]为True，则
- 返回。
- is_ok[x] := True
- util(x + a, a, b, is_ok, target)
- util(x + b, a, b, is_ok, target)
- 在主方法中执行以下操作：
- is_ok := 一个大小为(target + 1)并填充False的数组
- util(0, a, b, is_ok, target)
- 返回is_ok[target]
示例
让我们看看下面的实现来更好地理解：
def util(x, a, b, is_ok, target): if x > target: return if is_ok[x]: return is_ok[x] = True util(x + a, a, b, is_ok, target) util(x + b, a, b, is_ok, target) def solve(target, a, b): is_ok = [False] * (target + 1) util(0, a, b, is_ok, target) return is_ok[target] target = 26 A = 5 B = 7 print(solve(target, A, B))
输入
26, 5, 7
输出
True
更新于：2021年1月19日
392 次浏览
广告