动态规划—最长子序列问题

#include<iostream>
using namespace std;
int dp[100];
int f(int n)
{
    if (n == 1 || n == 0) return 1;
    if (dp[n] != 0) return dp[n];
    else
    {
        dp[n] = f(n - 1) + f(n -2);
        return dp[n];
    }
}
int main() {
    printf("%d", f(5));
}

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100;
int dp[N][N],f[N][N];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            cin >> f[i][j];
    for (int j = 1; j <= n; j++)
    {
        dp[n][j] = f[n][j];
    }

    for (int i = n - 1; i >= 1; i--)
    {
        for (int j = 1; j <= i; j++)
            dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + f[i][j];
    }

    cout << dp[1][1] << endl;
}