const int N=1010;

class Solution {
public:
    int mem[N];
    int dfs(vector<int>& cost, int x)
    {
        if(mem[x])return mem[x];

        int sum=0;
        if(x==1||x==0)sum=0;
        else sum=min(dfs(cost,x-1)+cost[x-1],dfs(cost,x-2)+cost[x-2]);
        mem[x]=sum;
        return sum;
    }

    int minCostClimbingStairs(vector<int>& cost) {
        int n=cost.size();
        // int ans=dfs(cost,n);
        int f[N];
        f[0]=f[1]=0;
        for(int i=2;i<=n;i++)
        {
            f[i]=min(f[i-1]+cost[i-1],f[i-2]+cost[i-2]);
        }
        return f[n];
    }
};

const int N = 3010;

class Solution {
public:
    int mem[N];
    int dfs(vector<int>& nums, int x) {
        if (mem[x])
            return mem[x];

        int res = 0;
        for (int i = 0; i < x; i++) {
            if (nums[i] < nums[x]) {
                res = max(res, dfs(nums, i) + 1);
            }
        }

        mem[x] = res;
        return res;
    }

    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        int res=-1e9;
        // for(int i=0;i<n;i++)
        // {
        //     res=max(res,dfs(nums,i)+1);
        // }
        int f[N];
        for (int i = 0; i < n; i++) {
            f[i] = 1;
            for (int j = 0; j < n; j++) {
                if (nums[j] < nums[i]) {
                    f[i] = max(f[i], f[j] + 1);
                }
            }
        }
        for(int i=0;i<n;i++)
        {
            res=max(res,f[i]);
        }
        return res;
    }
};

const int N = 10010;

class Solution {
public:
    int mem[N];

    int dfs(vector<int>& coins, int amount) {
        if (mem[amount])
            return mem[amount];
        int n = coins.size();
        if (amount == 0)
            return 0;
        int res = 1e9;
        for (int i = 0; i < n; i++) {
            if (amount >= coins[i])
                res = min(res, dfs(coins, amount - coins[i]) + 1);
        }
        mem[amount] = res;
        return res;
    }

    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        // int ans = dfs(coins, amount);
        // ans=ans==1e9?-1:ans;
        int f[N];
        memset(f, 0x3f, sizeof f);
        f[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < n; j++) {
                if(i>=coins[j])
                f[i]=min(f[i], f[i-coins[j]] + 1);
            }
        }
        return f[amount]>1e9?-1:f[amount];
    }
};

const int N=100010;

class Solution {
public:
    int mem[N];
    int dfs(vector<int>& sales,int x)
    {
        if(x<0)return 0;
        if(mem[x])return mem[x];
        int res=-1e9;
        res=max(sales[x],dfs(sales,x-1)+sales[x]);
        mem[x]=res;
        return res;
    }

    int maxSales(vector<int>& sales) {
        int n=sales.size();
        int f[N];
        int ans=-101;
        // for(int i=0;i<n;i++)
        // {
        //     ans=max(ans,dfs(sales,i));
        // }
        f[0]=sales[0];
        for(int i=1;i<n;i++)
        {
            f[i]=max(sales[i],f[i-1]+sales[i]);
        }
        for(int i=0;i<n;i++)
        {
            ans=max(ans,f[i]);
        }
        return ans;
    }
};

const int N=110;

class Solution {
public:
    int mem[N]={0};
    int dfs(int x)
    {
        if(mem[x])return mem[x];
        if(x==0)return 1;

        int res=0;
        for(int i=1;i<x;i++)
        {
            res=max(res,max(i*(x-i),dfs(x-i)*i));
        }
        return mem[x]=res;
    }

    int integerBreak(int n) {
        int ans;
        // ans=dfs(n);
        int dp[N];
        dp[0] = dp[1] = 1;
        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j < i; ++j) {
                dp[i] = max(dp[i], max(j * (i - j), dp[i - j] * j));
            }
        }
        ans=dp[n];
        return ans;
    }
};