算法问题（语言不限）

Question

一个二维坐标系，从（0,0）点出发，每次只能上下左右任意方向移动1，例如移动一步可以移动到（1,0）（0,1）（-1,0）（0，-1），问k步之后可以移动到多少个不同的位置（给出通式）？输出出来

Answer 1

可以倒着思考：假设第k步之后的不同位置为 f(k),f(k)是在f(k-1)基础上得到的，即f(k)最外层点是在f(k-1)最外层的点基础上出来的。那么可以得到一个关系式：f(k) = a(*)f(k-1)+b
（为什么是一次函数关系，很容易理解，拿第一步和第二步分析一下就看出来了,(*表示相乘的意思，不转义字符串就是斜体显示。看着别扭)）。得到f(0)=1,f(k) = f(k-1)+b,下面解决b:
每走一步，就有4个方向，所以是b = 4(*)k,所以最后的表达式为：f(k) = f(k-1)+4(*)k,f(0) = 1,代码实现：

public static int function(int k){
if(k<0) {
System.out.println("k must be bigger than 0");
return -1;
}
if(k==0) return 1;
//非递归方法
int fk = 0;
for(int i=1;i<=k;i++){
fk = fk + 4*i;
}
return fk+1;
}