algorithm - 我的 dp 方法的错误在哪里？ https ://www. spoj.com/problems/AE00/

Question

问题:

Byteman has a collection of N squares with side 1. How many different rectangles can he form using these squares?

Two rectangles are considered different if none of them can be rotated and moved to obtain the second one. During rectangle construction, Byteman can neither deform the squares nor put any squares upon any other ones.

Input The first and only line of the standard input contains one integer N (1 <= N <= 10000).

Output The first and only line of the standard output should contain a single integer equal to the number of different rectangles that Byteman can form using his squares.

Example For the input data: 6

the correct result is: 8

我的解决方案:

public class Rectangles {
    public void solve(int testNumber, Reader in, OutputWriter out) {
        try {
            while(true) {
                int N = in.ni();
                out.printLine(result(N));
            }
        } catch (Exception ee) { }
    }

    private long result(int n) {
        long[] res = new long[n+2];
        res[0] = 0;
        res[1] = 1;
        res[2] = 2;
        for(int i=3;i<=n;i++) {
            if(i%2 == 0) {
                res[i] = 3 + res[i-2];
            } else {
                res[i] = 1 + res[i-1];
            }
        }
        return res[n];
    }
}

我的 DP 方法:

For 0 squares: Result is 0
For 1 square: Result is 1: f(1) = 1
For 2 squares: Result is 2 : f(2) = 2
Now for f(3) = f(2) + 1 more square
With 1 more square we can only place it horizontally and hence 
f(3) = f(2)+1, generalizing, when n is ODD : f(n) = f(n-1) + 1
when n is EVEN: we use two squares which can make up to 3 rectangles, two horizontally([SQ] & [SQ][SQ]) plus one on top of the other, so total 3 possibilities, and hence f(n) when n is EVEN: f(n) = f(n-2) + 3.

Answer 1

对于给定的 N，所有可能的不同矩形是:

  1x1 1x2 1x3 1x4 ... 1x[N/1]
      2x2 2x3 2x4 ... 2x[N/2] // 2x1 is equals to 1x2 
          3x3 3x4 ... 3x[N/3] // 3x1 and 3x2 are equal to 1x3 and 2x3
                  ... 
                      Mx[N/M]   

[...] 表示整数部分(floor)或者换句话说，[N/M] 是整数除法。由于 N 不是很大，我们可以循环

C#代码:

private static int Solution(int value) {
  int result = 0;

  for (int i = 1; ; ++i) {
    int upTo = value / i;

    if (i > upTo)
      return result;

    result += (upTo - i + 1);
  }
}

演示:

  int[] tests = new int[] {
    0,
    1,
    6,
    9,
    10000,
  };

  string report = string.Join(Environment.NewLine, tests
    .Select(test => $"{test,5} -> {Solution(test),5}"));

  Console.Write(report);

结果:

    0 ->     0
    1 ->     1
    6 ->     8
    9 ->    13
10000 -> 46884