公式解説は LIS を求める問題に帰着していますが，素直な平面走査によっても解けます．

まず \((R_1,C_1),\dots,(R_N,C_N)\) は辞書順にソートされているとします．また簡単のため \((R_0,C_0)=(1,1),(R_{N+1},C_{N+1})=(H,W)\) として，\((1,1),(H,W)\) にもコインがあるとします．

\(\mathrm{dp}[i]\) を「\((R_0,C_0)\) から \((R_i,C_i)\) に移動するときに拾えるコインの枚数の最大値」とおくと求める値は \(\mathrm{dp}[N+1]\) であり，次が成り立ちます：

\[ \mathrm{dp}[i]=\max\{\mathrm{dp}[j]\mid R_j\leq R_i, C_j\leq C_i\}+1. \]

ただし \(\max\emptyset=0\) とします．\((R_0,C_0),\dots,(R_{N+1},C_{N+1})\) は昇順にソートしていたことを思い出せば，これは次のように書けます：

\[ \mathrm{dp}[i]=\max\{\mathrm{dp}[j]\mid j\leq i,C_j\leq C_i\}+1. \]

これは Segment Tree などを用いれば全体の計算量 \(O(N\log W)\) で計算できます．以下補足など

• 最終的に \((1,1),(H,W)\) の分の寄与を減ずる必要があります．
• 復元のためにセグ木上では値だけでなくその値を与える index も持つと楽です．
• この解法では各コインに価値が付いている場合も簡単に対応できます．

実装例(C++)

#include <bits/stdc++.h>
using namespace std;

#include <atcoder/all>
using namespace atcoder;

using P = pair<int, int>;
P op(P x, P y) { return x.first > y.first ? x : y; }
P e() { return {0, -1}; }

int main()
{
    int h, w, n;
    cin >> h >> w >> n;
    vector<P> coins(n + 2);
    coins[0] = {0, 0};
    for (int i = 1; i <= n; i++)
    {
        int r, c;
        cin >> r >> c;
        coins[i] = {r - 1, c - 1};
    }
    coins[n + 1] = {h - 1, w - 1};
    n += 2;
    sort(coins.begin(), coins.end());

    vector<int> dp(n), prv(n);
    segtree<P, op, e> seg(w);
    for (int i = 0; i < n; i++)
    {
        int c = coins[i].second;
        auto p = seg.prod(0, c + 1);
        dp[i] = p.first + 1;
        prv[i] = p.second;
        if (seg.get(c).first < dp[i]) seg.set(c, {dp[i], i});
    }

    cout << (dp[n - 1] - 2) << "\n";

    vector<char> moves;
    for (int idx = n - 1; idx != 0; idx = prv[idx])
    {
        auto [x1, y1] = coins[idx];
        auto [x2, y2] = coins[prv[idx]];
        for (; x2 < x1; x1--) moves.push_back('D');
        for (; y2 < y1; y1--) moves.push_back('R');
    }
    reverse(moves.begin(), moves.end());
    for (auto c : moves) cout << c;
    cout << "\n";
}