计数型

K 个逆序对数组 lc629.

状态：f[i][j]表示前i个数字，恰好构成j个逆序对

转移：f[i][j]=f[i][j-1]-f[i-1][j-i]+f[i-1][j]

边界：f[n][k]

509. Fibonacci Number

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Given n, calculate F(n).

public int fib(int n) {
    int[] f = new int[]{0, 1, 0};
    for (int i = 2; i <= n; i++) {
        f[i % 3] = f[(i - 1) % 3] + f[(i - 2) % 3];
    }

    return f[n % 3];
}