dynamic - 配列内の数値の合計

Question

私はプログラミングが初めてで、オンライン審査システムの問題を解決しようとしています。非常に興味深く重要に見える問題がありますが、残念ながらそれを解決する方法がわかりません。ヒントをいただければ幸いです。

問題は次のとおりです。入力として配列が与えられます。数値の合計が同じである 2 つの部分配列がある場合は 1 を出力し、そうでない場合は 0 を出力します。

入力: 2 1 1 出力: 1 入力: 3 2 5 3 出力: 1 入力: 3 1 4 7 出力: 0

ありがとう

Answer 1

これは、パーティションの問題 (または少なくともパーティションの問題の変形) として知られています。これは、動的計画法のソリューションと呼ばれるものを必要とする問題です。これは、プログラミングを学び始めたばかりの人にとってはかなり高度な問題です。いくつかの簡単な課題から始めることをお勧めします。

ただし、この野獣に取り組むことに興味がある場合は、次のリンクをチェックしてください: http://people.csail.mit.edu/bdean/6.046/dp/ . このページの「パーティションの問題」へのリンクは、実用的な解決策のビデオ説明を示しています。