Question

n乘n个方格中有多少个不同的正方形

Answer 1

题目：？–微软、百度面试题解答：边长为1的一共有n*n个；边长为2的，有（n-1）*（n-1）个，因为正方形的左上角顶点有这么多可以选择的情况。如此类推下去，最后是边长为n的一共有1个，就是最大的这个正方形所以一共有的正方形是：
f(n)=1^2+2^2+3^2+…+n^2个
令s=1^2+2^2+…+n^2。其结果可猜测到是关于n的三次式，设s=an^3+bn^2+cn+d.分别取n=0，s=1；n=1，s=1；n=2，s=5；n=3，s=14。列出四个方程可确定a，b，c，d的值，并化简后即n（n+1）（2n+1）/6。
采用的方法依然是首先固定左上角起点，查看右下角顶点可以选择的种类。