#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <unordered_map>
using namespace std;

class Solution
{
public:
    int fib(int n)
    {
        if (n <= 1)
            return n;

        vector<int> dp(n + 1);
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; ++i)
        {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    int climbStairs(int n)
    {
        if (n <= 1)
            return n;
        vector<int> dp(n + 1);
        dp[1] = 1;
        dp[2] = 2;

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

    int minCostClimbingStairs(vector<int> &cost)
    {
        int n = cost.size();
        vector<int> dp(n + 1);
        dp[0] = 0;
        dp[1] = 0;

        for (int i = 2; i <= n; ++i)
        {
            dp[i] = std::min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }

        return dp[n];
    }

    int uniquePaths(int m, int n)
    {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        for (int i = 0; i < m + 1; ++i)
            dp[i][0] = 1;
        for (int j = 0; j < n + 1; ++j)
            dp[0][j] = 1;

        for (int i = 1; i < m; ++i)
        {
            for (int j = 1; j < n; ++j)
            {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m - 1][n - 1];
    }

    int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid)
    {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1)
            return 0;

        vector<vector<int>> dp(m, vector<int>(n, 0));

        for (int i = 0; i < m; ++i)
        {
            if (obstacleGrid[i][0] == 1)
                break;
            dp[i][0] = 1;
        }

        for (int j = 0; j < n; ++j)
        {
            if (obstacleGrid[0][j] == 1)
                break;
            dp[0][j] = 1;
        }

        for (int i = 1; i < m; ++i)
        {
            for (int j = 1; j < n; ++j)
            {
                if (obstacleGrid[i][j] == 1)
                    continue;
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m - 1][n - 1];
    }

    int integerBreak(int n)
    {
        vector<int> dp(n + 1);
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i <= n; ++i)
        {
            for (int j = 1; j < i; ++j)
                dp[i] = std::max(dp[i], std::max(j * (i - j), j * dp[i - j]));
        }

        return dp[n];
    }

    int numTrees(int n)
    {
        vector<int> dp(n + 1);
        dp[0] = 1;

        for (int i = 1; i <= n; ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }

        return dp[n];
    }

    // 杨辉三角
    vector<vector<int>> generate(int numRows)
    {
        vector<vector<int>> res;
        for (int i = 0; i < numRows; ++i)
        {
            vector<int> v(i + 1, 1);
            res.push_back(v);
        }

        for (int i = 2; i < numRows; ++i)
        {
            for (int j = 1; j < res[i].size() - 1; ++j)
            {
                res[i][j] = res[i - 1][j - 1] + res[i - 1][j];
            }
        }

        return res;
    }

    int rob(vector<int> &nums)
    {
        if (nums.size() <= 1)
            return nums[0];

        vector<int> dp(nums.size());
        dp[0] = nums[0];
        dp[1] = std::max(nums[1], dp[0]);

        for (int i = 2; i < nums.size(); ++i)
        {
            dp[i] = std::max(dp[i - 2] + nums[i], dp[i - 1]);
        }

        return dp[nums.size() - 1];
    }

    int rob_range(vector<int> &nums, int s, int e)
    {
        if (s > e)
            return INT32_MIN;
        if (s == e)
            return nums[s];

        vector<int> dp(nums.size());
        dp[s] = nums[s];
        dp[s + 1] = std::max(nums[s + 1], dp[s]);

        for (int i = s + 2; i <= e; ++i)
        {
            dp[i] = std::max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[e];
    }
    int rob2(vector<int> &nums)
    {
        if (nums.size() == 0)
            return 0;
        if (nums.size() == 1)
            return nums[0];

        int res1 = rob_range(nums, 1, nums.size() - 2);
        int res2 = rob_range(nums, 1, nums.size() - 1);
        int res3 = rob_range(nums, 0, nums.size() - 2);

        return std::max({res1, res2, res3});
    }
};

int main()
{
    return 0;
}