DP入门

动态规划（DP）基本思想

保存子问题的结果，避免重复计算
用额外的数据结构保存（备忘）
空间换时间
大问题可以由子问题推出（状态转移）

斐波那契数列

斐波那契数列前46项：（int范围）

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903……

斐波那契数列前92项：（long long 范围）

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 14472334024676221, 23416728348467685, 37889062373143906, 61305790721611591, 99194853094755497, 160500643816367088, 259695496911122585, 420196140727489673, 679891637638612258, 1100087778366101931, 1779979416004714189, 2880067194370816120, 4660046610375530309, 7540113804746346429……

斐波那契数列时间复杂度分析

分析

指数级别复杂度O($ 2^n $)
大问题由子问题组合而成
重叠子问题，重复计算
空间换时间，避免重复计算

状态转移方程：

\[ f(n)= \begin{cases} 1\qquad \qquad \qquad \qquad \qquad \ n = 1\ |\ n = 2 \\ f(n-1) + f(n-2) \qquad \,\, n>2 \end{cases} \]

递推（变量）递推（数组）递归递归 + 备忘（DP）

int f(int n){
    int a, b, c;
    a = b = 1;
    for(int i = 3; i <= n; i++){
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}

int main(){
    int n;
    cin >> n;
    cout << f(n);
    return 0;
}

int f(int n){
    int a[n + 5];
    a[1] = a[2] = 1;
    for(int i = 3; i <= n; i++){
        a[i] = a[i - 1] + a[i - 2];
    }
    return a[n];
}

int main(){
    int n;
    cin >> n;
    cout << f(n);
    return 0;
}

int fib(int n){
    if(n == 1 || n == 2) return 1;
    return fib(n - 1) + fib(n - 2);
}

int main(){
    int n;
    cin >> n;
    cout << f(n);
    return 0;
}

int memory[10005];
int fib2(int n){
    if(memory[n] != 0) return memory[n];    
    if(n == 1 || n == 2) return 1;
    cout << 1 << endl;
    return memory[n] = fib2(n - 1) + fib2(n - 2);
}

int main(){
    int n;
    cin >> n;
    cout << f(n);
    return 0;
}

P1216 [USACO1.5] [IOI1994]数字三角形 Number Triangles

DP(递归 + 备忘）DP(递推 + 填表)DP(递推 + 填表 + 压维）

#include<iostream>
#include<cstring>
using namespace std;

const int N = 1005;
int a[N][N];
int memory[N][N];

int r;

int max_sum(int i, int j){
    if(memory[i][j] != -1) return memory[i][j];
    if(i == r) return memory[i][j] = a[i][j];
    return memory[i][j] = max(max_sum(i + 1, j), max_sum(i + 1, j + 1)) + a[i][j];
}

int main(){
    memset(memory, -1, sizeof(memory));
    cin >> r;
    for(int i = 1; i <= r; i++){
        for(int j = 1; j <= i; j++){
            cin >> a[i][j];
        }
    }
    cout << max_sum(1, 1);
    return 0;
}

#include<iostream>
using namespace std;

const int N = 1005;
int a[N][N];
int memory[N][N];
int r;

void max_sum(){
    for(int i = 1; i <= r; i++){
        memory[r][i] = a[r][i];
    }
    for(int i = r - 1; i >= 1; i--){
        for(int j = 1; j <= i; j++){
            memory[i][j] = max(memory[i + 1][j], memory[i + 1][j + 1]) + a[i][j];
        }
    }
}

int main(){
    cin >> r;
    for(int i = 1; i <= r; i++){
        for(int j = 1; j <= i; j++){
            cin >> a[i][j];
        }
    }
    max_sum();
    cout << memory[1][1];
    return 0;
}

#include<iostream>
using namespace std;

const int N = 1005;
int a[N][N];
int memory[N];
int r;

void max_sum(){
    for(int i = 1; i <= r; i++){
        memory[i] = a[r][i];
    }
    for(int i = r - 1; i >= 1; i--){
        for(int j = 1; j <= i; j++){
            memory[j] = max(memory[j + 1], memory[j]) + a[i][j];
        }
    }
}

int main(){
    cin >> r;
    for(int i = 1; i <= r; i++){
        for(int j = 1; j <= i; j++){
            cin >> a[i][j];
        }
    }
    max_sum();
    cout << memory[1];
    return 0;
}