Answer is $2n$. Consider $\Delta_{n+1,x} \Delta_{n+1,y} P(x,y)|_{x=y=0} = \sum\limits_{j=0}^n \sum\limits_{k=0}^n (-1)^{j+k} \binom nj \binom nk \frac{1}{1+j+k} \ne 0$, so $\deg P\ge 2n$. Construction $P(x,y)=Q(x+y)$ such that $Q(a)=\frac{1}{a+1}$ for $a=0,\cdots,2n$

Here is another solution. Observation: We can assume no term $x^ay^b$ appears where $\max\{a,b\} \ge n+1$. To see this, if $a\ge n+1$ we can divide $x^a$ by $x(x-1)\cdots (x-n)$ and replace it with the remainder. Nothing will change. Now let $P_j(y)=P(j,y)$ for $0\le j\le n$. As discussed earlier, $\deg P_j \le n$ By Lagrange Interpolation, there exists unique reals $a_{n,j}, \cdots, a_{0,j}$ such that $P_j(y)=a_{n,j}y^n + a_{n-1,j} y^{n-1} + \cdots + a_{1,j}y+ a_{0,j}$. Now let $A_k$ be the unique polynomial of degree at most $n$ such that $A_k(x)=a_{x,k}$. This implies $P(x,y)=A_n(x)y^n + A_{n-1}(x)y^{n-1} + \cdots + A_0(x)$, so there is one unique $P$ such that no $x^ay^b$ where $\max\{a,b\} \ge n+1$ appears. We just need to check $[x^ny^n] P(x,y) \ne 0$.

CANBANKAN wrote: Here is another solution. Observation: We can assume no term $x^ay^b$ appears where $\max\{a,b\} \ge n+1$. To see this, if $a\ge n+1$ we can divide $x^a$ by $x(x-1)\cdots (x-n)$ and replace it with the remainder. Nothing will change. Now let $P_j(y)=P(j,y)$ for $0\le j\le n$. As discussed earlier, $\deg P_j \le n$ By Lagrange Interpolation, there exists unique reals $a_{n,j}, \cdots, a_{0,j}$ such that $P_j(y)=a_{n,j}y^n + a_{n-1,j} y^{n-1} + \cdots + a_{1,j}y+ a_{0,j}$. Now let $A_k$ be the unique polynomial of degree at most $n$ such that $A_k(x)=a_{x,k}$. This implies $P(x,y)=A_n(x)y^n + A_{n-1}(x)y^{n-1} + \cdots + A_0(x)$, so there is one unique $P$ such that no $x^ay^b$ where $\max\{a,b\} \ge n+1$ appears. We just need to check $[x^ny^n] P(x,y) \ne 0$. This exact approach can be used to prove combinatorial nullstellensatz, and also the key idea to IMO 2007 P6