「教えて!ピックアップ」リリース!

単刀直入失礼いたします。
プログラミングにおける「制限なし部分和」の配列の前準備について質問があります。
★普通の部分和の配列処理
dp[i+1][j] |= dp[i][j];
dp[i+1][j] |= dp[i][j-a[i]];
★制限つき部分和の配列処理
dp[i+1][j] |= dp[i][j];
dp[i+1][j] |= dp[i+1][j-a[i]];

なぜ、dp[i+1]にするだけで制限なし(無限回)の和が処理されるのでしょうか。
わたしの予想としては、0にならないからだと考えているのですが…

ご回答いただけると幸いです。

質問者からの補足コメント

  • 個数制限なし部分和について追記です。

    a=[2,4,5,6], B=15

    aの配列の要素を制限なく使った時に、Bに一致するといった和のことを指します。
    この場合だと、5+5+5、4+6+5などなど...

      補足日時:2022/11/23 16:22

A 回答 (2件)

ふむふむ.



では dp[i][j] とはどのような意味を持っているのだろうか. 例えば, どのような値だとどのようなことを表しているのかとか, 言葉で表せるだろうか.

あとあなたの予想に関してだけど, 何が「0にならない」という理由によって「dp[i+1]にするだけで制限なし(無限回)の和が処理される」といっている? そしてその根拠は?
    • good
    • 0

その「制限なし部分和」とやらがどのようなものなのかを書いてもらえないだろうか.

    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています


このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング