問題タブ [bottom-up]

私が持っているこの問題をチェックしてください：

「あなたと 8 歳の甥のエルモは、簡単なカード ゲームをすることにしました。ゲームの開始時に、カードは表向きに長い列に並んで配られます。各カードは、異なる数のポイントの価値があります。カードが配られたら、あなたとエルモは、すべてのカードがなくなるまで、列から左端または右端のカードを順番に取り除きます. 各ターンで、2枚のカードのどちらを取るかを決めることができます. ゲームの勝者はプレーヤーです.ゲーム終了時に最も多くのポイントを集めたカード. アルゴリズムのクラスを受講したことがないので、エルモは明らかな貪欲な戦略に従います.彼の番になると、エルモは常により高いポイント値を持つカードを取ります. あなたの仕事は戦略を見つけることです. (このように小さな子供を殴るのは意地悪に思えるかもしれませんが、エルモは大人に勝たせてしまうのを絶対に嫌がります)。

与えられた最初のカードの並びから、エルモと対戦して獲得できる最大ポイント数を決定するアルゴリズムを説明、解析してください."

この問題の理論的な作業のほとんどは既に完了しています。たとえば、DP に必要なオプティマス部分構造のデモンストレーションを行い、ゲームがどのように行われるかを説明する Recursive 非効率的な形式を定義しました。次のステップは、この問題を効率的に解決するボトムアップ アルゴリズムを設計することです。それが役立つ場合は、トップダウンのメモ化ソリューションを設計することです。私はそれらのどれもできません。この問題をどのように解決しますか？

最初に Java クラスを作成することにより、ボトムアップ アプローチを使用して Web サービスを作成しようとしています。私の実装は次のようになります。

AddNumberRequest クラスは次のとおりです。

Web サービスは公開されていますが、soapui からサンプル リクエストを生成すると、リクエストは次のようになります。

サンプルリクエストが次のようになるように、アノテーションを使用してメソッドのJava実装を作成するだけの方法はありますか?

ws:addNumbers (デフォルトでは operationName によって生成される) 要素をまったく持たずに、たとえば addNumberRequest などのラッパー要素の名前を決定できるようにしたいと考えています。

Web 開発の 2 つのアプローチの違いを理解しています。しかし、特定のアプローチが他のアプローチよりも有利な状況はありますか? そして、一方の欠点とは？

私は記事でこれを読みました: トップダウンでは、 WSDL を変更する場合、JAVA クラスを変更する必要があります。ボトムアップでは、JAVA クラスで行われた変更はビルド中に処理されます。

他の ？

次の文脈自由文法を見てみましょう。

Pであること：

この文法によって生成された式を、ボトムアップ パーサーと長さ 1 のルックアヘッド バッファー (LAB) を使用して解析しようとしています (おそらく、推測やバックトラッキングなしで行う必要があります)。

ここで、スタックと LAB が与えられた場合、スタックを削減する方法、またはスタックをまったく削減するか別のトークンをプッシュするかについて、いくつかの可能性がしばしばあります。

現在、私はこの決定木を使用しています：

スタックの上位 n 個のトークンと LAB がルールの右側の開始点である場合、次のトークンをスタックにプッシュします。

それ以外の場合は、スタックの一番上にあるトークンの最大数を減らします。つまり、一番上の項目を削減すると同時に、一番上の 3 つの項目を削減できる場合は、後者を行います。

そのような削減が不可能な場合は、別のトークンをスタックにプッシュします。

すすいで繰り返します。

これは (!) 動作するように見えますが、非常に多くのルール検索、一致するプレフィックスの検索などが必要です。これを O(NM) で実行することはできません。

削減するかプッシュ（シフト）するかを決定するための標準的な（そしておそらく賢明な）アプローチは何ですか？削減の場合は、どの削減を適用しますか？

コメントと回答をお寄せいただきありがとうございます。

私が学んだことは、動的計画法 (DP) には、トップダウンとボトムアップの 2 種類があるということです。

トップダウンでは、メモ化とともに再帰を使用します。ボトムアップでは、配列 (テーブル) を埋めるだけです。

また、これらの方法はどちらも同じ時間の複雑さを使用します。個人的には、トップダウンのアプローチの方が従うのがより簡単で自然だと思います。DP の特定の問題は、どちらのアプローチでも解決できるというのは本当ですか? それとも、2 つの方法のいずれかでしか解決できない問題に直面することはありますか?