Answer : 👇
class Solution
{
public:
int dp[50] = {0};
int climbStairs(int n)
{
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; ++i)
{
dp[i] = dp[i - 2] + dp[i - 1];
}
return dp[n];
}
};
Answer : 👇
class Solution
{
int dp[100005][2]; // for memoizations
int n;
int find(vector<int> &v, int i, bool buy, int k)
{
if (n == 1 || i == n || k == 0)
return 0;
if (dp[i][buy] != -1)
return dp[i][buy];
if (buy)
{
return dp[i][buy] = max(-v[i] + find(v, i + 1, !buy, k), find(v, i + 1, buy, k));
}
else
{
return dp[i][buy] = max(v[i], find(v, i + 1, buy, k));
}
}
public:
int maxProfit(vector<int> &prices)
{
n = prices.size();
memset(dp, -1, sizeof(dp));
return max(0, find(prices, 0, 1, 1));
}
/*-----------------RECURSIVE CODE 👇 -------------------------*/
class Solution
{
int n;
int dp[30005][2];
int find(vector<int> &v, int i, bool buy)
{
if (n == 1 || i == n)
return 0;
if (dp[i][buy] != -1)
return dp[i][buy];
if (buy)
{
return dp[i][buy] = max((find(v, i + 1, !buy) - v[i]), find(v, i + 1, buy));
}
else
{
return dp[i][buy] = max(v[i] + find(v, i + 1, !buy), find(v, i + 1, buy));
}
}
public:
int maxProfit(vector<int> &prices)
{
n = prices.size();
memset(dp, -1, sizeof(dp));
return max(find(prices, 0, 1), 0);
}
};
/*-----------------Top Down DP 👇 -------------------------*/
/*-----------------RECURSIVE CODE 👇 -------------------------*/
class Solution
{
int n;
// for dp[N][buy][k]
int dp[100001][2][3];
int find(vector<int> &v, int i, bool buy, int k)
{
if (n == 1 || i == n || k == 0)
return 0;
if (dp[i][buy][k] != -1)
return dp[i][buy][k];
if (buy)
{
return dp[i][buy][k] = max(find(v, i + 1, !buy, k) - v[i], find(v, i + 1, buy, k));
}
else
{
return dp[i][buy][k] = max(v[i] + find(v, i + 1, !buy, k - 1), find(v, i + 1, buy, k));
}
}
public:
int maxProfit(vector<int> &prices)
{
n = prices.size();
memset(dp, -1, sizeof(dp));
return find(prices, 0, 1, 2);
}
};
/*-----------------Top Down DP 👇 -------------------------*/
Category: Python | General Programming
Relavent Tags: Dynamic Programming