動的プログラミング "Solitare Board Game"

Question

私はプログラミングの問題を抱えていますが、どちらの方向から始めればいいですか？

問題は以下の通りである：我々はそれに数値（負、ゼロを有するグリッドの各正方形を有するいくつかのn×nの正方形ボード（本質的に二次元アレイ）を有する場合

、または正）。このゲームのガイドラインは、ボード上の任意の位置で「トークン」から始めることができ、トークンを（任意の順序で）右または下にのみ移動できます。あなたが入力した各四角形につき、その合計をあなたの得点から加算または減算し、右または下端の四角形から移動する前に可能な限り高い得点を累積することです。

これは私が過去に見たダイナミックプログラミングの問題と似ていますが、私は本質的にダイナミックプログラミングの方法を取らずにどこから始めたらいいか分かりません。テーブルを右端と下端の各四角形に追加しますが、2 n個のテーブル（サイズn^2のテーブルが残っていて、ランタイムはひどくなります）。

この問題の出発点として、できるだけ効率的な時間と空間としてアルゴリズムを維持しながら、可能な限り高いスコアを達成するために？

Answer 1

これを正しく理解すれば、y OUはただのエントリが

table[-1][j] = INT_MIN for all j 

と

table[i][-1] = INT_MIN for all i 

（表は実際のボードの最大スコアとボード用のテーブルであると

table[i][j] = board[i][j] + max(table[i][j-1], table[i-1][j]) 

あるn×nのテーブルを作ることができます）