DP？メモリ削減テクニック

今やっていた、SRM 430 DIV1 Medium TwinTowns。
このrng_58さんの解答を参考に書いた下のコード。

typedef long long ll; typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pii> vpii;
const int INF = 0x3f3f3f3f; const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
#define X(m, i) (((m)>>((i)*2))&3)
int dp[1<<20];
struct TwinTowns {
	vector <int> optimalTwinTowns(vector <int> x, vector <int> y, int maxPartners, int minDistance) {
		int n = x.size();
		mset(dp, INF);
		dp[0] = 0;
		rep(i, n) rep(j, n) if(i < j) {
			int d = abs(x[i] - x[j]) + abs(y[i] - y[j]);
			if(d >= minDistance) {
//※1
				for(int mask = (1<<(n*2))-1; mask >= 0; mask --) {
					int d1 = X(mask, i), d2 = X(mask, j);
					if(d1 < maxPartners && d2 < maxPartners) {
						int mask2 = mask + (1<<(i*2)) + (1<<(j*2));
						dp[mask2] = min(dp[mask2], dp[mask] + d);
					}
				}
			}
		}
		pii p = pii(0, 0);
		rep(mask, 1<<(n*2)) if(dp[mask] != INF){
			cout << bitset<20>(mask) << ": " << dp[mask] << endl;
			int count = 0;
			rep(i, n) count += X(mask, i);
			p = max(p, pii(count / 2, -dp[mask]));
		}
		vi v;
		v.pb(p.first); v.pb(-p.second);
		return v;
	}
};

この※1のfor、大きい方からmaskを回しているが、逆にすると答えが合わない。何故なら、そうすると同じペアで複数回作ってしまうからだ。
これは実際、そのままのDPではない。
本当は状態としてi,jのが必要であるが、順番を適切に上書きしていくことによって、メモリの削減ができる、という形のものである(？)。
これは二次元グリッドで、上一行だけ持って、上書きしていくようなものか？
実際、これをメモ化再帰で書こうとすると単純には上手くいかなくて、どうしても再現するならグローバルな変数が必要な気がする(実際にはよくわからない)
自分はDPをいつもメモ化再帰の形で書いているが、このテクニックの形、またそれを読むことにも慣れておく必要がありそうだ