2dの配列から最小の和のパスを見つける

Question

以下のアルゴリズムについて考えてみましょう。

各ノードに値があるとします。 0,0から始まり、n,mに到達する必要があります。 i,jからi+1,jまたはi,j+1に行くことができます。各ブロックを踏むと、そのブロックの値が現在のスコアに加算されます。あなたがいつも最後に肯定的なスコアを持つn,m（可能なパスを通して）に達することができるように、あなたが携行しなければならない最小の最初のスコアは何ですか？

例：

Matrix ->  2 3 4 
       -5 -6 7 
       8 3 1 

回答 - > 6 - パス2、-5、-6,3,1我々は1に着陸するとき、我々は正のスコアを持つように、我々は6の初期スコアを必要としますof 1

私はブルートフォースとダイナミックプログラミングを使用してこれを行うことができますが、これよりも良いアプローチを考えています。私はこれを行うことができるので、思考/アイデアを実装する必要はありません。 。多くの検索アルゴリズムがあります

Answer 1

が、私はあなたがこれらのウィキペディアのページを読んで奨励：

https://en.wikipedia.org/wiki/Pathfinding

https://en.wikipedia.org/wiki/Tree_traversal

一つの可能​​な解決策を、グラフ化し、それに最短経路アルゴリズムを適用するための配列を変換することで、もう1つの解決策は、A *などのIAアルゴリズムを使用することです。 （スターをprounced）*のためのウィキペディアに

リンク：

https://en.wikipedia.org/wiki/A*_search_algorithm