a111: 12149 - Feynman

解題心得

總是沒辦法自己想出來......紀錄一下推導。

以 4*4 的方形為例，會有：

1*1 的方形，共 16 個

2*2 的方形，共 9 個

3*3 的方形，共 4 個

4*4 的方形，共 1 個

基本邏輯就是把1~n邊長都找過一遍，看這樣的情況下能有幾種可能。又長度為i的情況下，會有(n-i)*(n-i)的可能，也就剛好是1^2+2^2+3^3+.....+n^2了。

用dp的話，就把每次結果存起來，算當下的就是把前一個加上自己的n^2就好。

程式碼 

#include <iostream>
using namespace std;

int main()
{
	int memo[101] = { 0,1 }, n;
	for (int i = 2; i < 101; i++)
		memo[i] = memo[i - 1] + i * i;
	while (cin >> n && n != 0)
		cout << memo[n] << endl;
	return 0;
}