>>17
> 重なることなくa+b個の格子点を覆っていたとしても
これはだめだね。すでにある一本の直線が新しく増えた格子点のうち2個を通るような場合もあるから。
（例） 傾き−1の直線をa+b本引いて全体を覆った場合

> それは変更可能ではないのか？
というか、変更する場合も考えないとまずい。
D(a+1,b+1)では、D(a,b)では引けなかった直線x=a,y=bを引いても構わない。
また、D(a,b)が最小の本数で覆われていることはD(a+1,b+1)が最小の本数で覆われるための
必要条件ではないのでそうでない場合も考慮する必要がある。

> D(a+1,b)やD(a,b+1)のときN(a+b+1)だといえるのだろうか？
ここは特に問題ない。aとbの一方が1でその差が任意の整数である場合からスタートしているから。

x軸方向にm個、y軸方向にn個、並んだ格子点をすべて覆うように直線を引くとき、
仮にx軸やy軸に平行な直線をひいてはならないという条件だとすると、
mかnの少なくとも一方が1のときは、一本の直線では1つの点しか覆えないので、m本または
n本、つまりどちらの場合も(m+n-1)本の直線が必要。
mとnがともに1でないときは、少なくともこの長方形の領域の周上にある(2m+2n-4)個の点が
覆われる必要があるが、一本の直線では高々2点までしか覆うことができないので、
(m+n-2)本の直線が必要。
よってどちらの場合も直線の本数を(m+n-2)より少なくすることはできない。

問題ではx軸やy軸に平行な直線を引いても構わないが、x=a,y=bは引けないので、
x軸またはy軸に平行な直線だけですべての点を覆うことはできない。
y軸に平行な直線がk本、x軸に平行な直線がl本あるとすると、これらで覆われない点は
(a-k+1)*(b-l+1)個あるが、これらをすべて覆う直線の本数は、上記より、(a-k+1)+(b-l+1)-2=a+b-k-l
より少なくすることはできない。よって、すべての点を覆うのに最低限必要な直線の数は
k+l+(a+b-k-l)=a+b

…って、原点を除かなきゃならんのか。めんどいなぁ…