Pythonでの3回の操作で配列の合計をKにできるかどうかを確認します

numsと呼ばれる数値のリストがあり、正の値Kもあるとします。これらの3つの演算のいずれかをnums-

• 1つの数値を負にする
• 番号自体に番号のインデックス（インデックス1から開始）を追加します
• 番号自体から番号のインデックスを引きます。

最後に、各要素に対してこれらの操作を1回だけ実行することにより、配列の合計がkになるときに、指定された配列を変換できるかどうかを確認する必要があります。

したがって、入力がnums =[1,2,3,7] k =8の場合、出力はTrueになります。これは、2と3から2と3のインデックスを減算して、[1、0、 0、7]なので、合計は8=kになります。

これを解決するには、次の手順に従います-

• サイズ：=100
• 関数is_ok（）を定義します。これには、i、total、k、nums、tableが必要です
• n：=numsのサイズ
• 合計<=0の場合、
  • Falseを返す
• i> =nの場合、
  • 合計がkと同じ場合、
    • Trueを返す
• Falseを返す
• table [i、total]が-1でない場合、
  • リターンテーブル[i、合計]
• table [i、total]：=1（is_ok（i + 1、total-2 * nums [i]、k、nums、table）がゼロ以外またはis_ok（i + 1、total、k、 nums、table）はゼロ以外）、それ以外の場合は0
• table [i、total]：=1 when（is_ok（i + 1、total-（i + 1）、k、nums、table）or table [i、total]）、それ以外の場合は0
• table [i、total]：=1 when（is_ok（i + 1、total + i + 1、k、nums、table）or table [i、total]）、それ以外の場合は0
• リターンテーブル[i、合計]
• メインの方法から次のようにします-
• total：=numsのすべての要素の合計
• table：=サイズと同じ長さで、-1で埋める配列
• 0からサイズの範囲のiの場合は、
  • table [i]：=サイズと同じ長さで、-1で埋める配列
• return is_ok（0、total、k、nums、table）

理解を深めるために、次の実装を見てみましょう-

例

size = 100
def is_ok(i, total, k, nums, table):
   n = len(nums)
   if total <= 0:
      return False
   if i >= n:
      if total == k:
         return True
      return False
   if table[i][total] != -1:
      return table[i][total]
   table[i][total] = is_ok(i+1, total - 2 * nums[i], k, nums, table) or is_ok(i+1, total, k, nums, table)
   table[i][total] = is_ok(i+1, total - (i+1), k, nums, table) or table[i][total] table[i][total] = is_ok(i+1, total + i + 1, k, nums, table) or table[i][total]
   return table[i][total]
def solve(nums, k):
   total = sum(nums)
   table = [-1]*size
   for i in range(size):
      table[i] = [-1]*size
   return is_ok(0, total, k, nums, table)
nums = [1,2,3,7]
k = 8
print(solve(nums, k))

入力

[1,2,3,7], 8

出力

True