まず、同じ行で \(3\) つまでしか拾えないという条件を無視すれば、シンプルな動的計画法 (\(f_{i,j} :=(1, 1)\)から \((i, j)\) までの経路についての最大値　とすればよい) で答えを求められます。

\(3\) つしかないという条件から各行では拾う場所の組を全部試す方針が考えられるかもしれませんが、少なくとも左端と右端の情報は必要になると思われ、計算量が \(3\) 乗になってしまいます。

しかし、初めの \(f\) の情報に、今いる行 (\(i\) 行目)で既に何回拾ったかという情報を組み込み、\(f_{i,j,k}\) を計算していくと、各 \(i,j,k\) について遷移が \(\mathrm{O}(1)\) 通りしかなく (\(i+1\) に行く場合は \(k=0\) としてリセットし、\(i\) のままであれば \(k\) をそのまま考慮する)、全体でも \(\mathrm{O}(RC)\) で計算可能です。

このように、区間から定数個選ぶ設定では区間の状態を状態として追加で持つことで高速化できる場合がよくあります。

実装例(C++)