70.

CLIMBING STAIRS (RECURSSIVE)

[Link]

int climbStairs(int n) {
if(n==0 or n==1){
return 1;
}
return climbStairs(n-1)+climbStairs(n-2);
}

70. CLIMBING STAIRS (memoisation)

[Link]

int cs(int n,vector<int> & dp){

if(dp[n]!=-1){
return dp[n];
}
return dp[n]=cs(n-1,dp)+cs(n-2,dp);
}
int climbStairs(int n) {
vector<int> dp(n+1,-1);
dp[0]=1;
dp[1]=1;
return cs(n,dp);
}

70. CLIMBING STAIRS (Tabulation)

[Link]

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

\\\
(Improvised Tabulation)
\\\

int climbStairs(int n) {
int a=1;
int b=1;
if(n==0 or n==1){
return 1;
}
int c=-1;
for(int i=2;i<=n;i++){
c=a+b;
a=b;
b=c;
}
return c;
}

403. FROG JUMP

// bool dfs(int curr_pos, int last_jump, const set<int>& stone_set, int last_stone)
{
// if (curr_pos == last_stone) return true;
// if (curr_pos > last_stone) return false;

// for (int jump = last_jump - 1; jump <= last_jump + 1; ++jump) {

// if (jump >= 1 && stone_set.count(curr_pos + jump)) {
// if (dfs(curr_pos + jump, jump, stone_set, last_stone)) {
// return true;
// }
// }
// }
// return false;
// }

map<pair<int, int>, bool> m;

bool dfs(int curr_pos, int last_jump, const set<int>& stone_set, int

last_stone){
pair<int, int> state = {curr_pos, last_jump};

if ([Link](state) != [Link]()) {
return m[state];
}

if (curr_pos == last_stone) return true;

for (int jump = last_jump - 1; jump <= last_jump + 1; ++jump) {

if (jump >= 1 && stone_set.count(curr_pos + jump)) {
if (dfs(curr_pos + jump, jump, stone_set, last_stone)) {
return m[state] = true;
}
}
}

return m[state] = false;

}

bool canCross(vector<int>& stones) {

if ([Link]() < 2 || stones[1] != 1) return false;

set<int> stone_set([Link](), [Link]());

int last_stone = [Link]();

return dfs(1, 1, stone_set, last_stone);

}

198. HOUSE ROBBER (MEMORISATION)

int rec(int curr,vector<int>& nums,vector<int> &s){

if(curr>=[Link]()){
return 0;
}
if(s[curr]!=-1){
return s[curr];
}
s[curr]= max(nums[curr]+rec(curr+2,nums,s),rec(curr+1,nums,s));
return s[curr];
 }
int rob(vector<int>& nums) {
vector<int> s([Link]()+1,-1);
return rec(0,nums,s);
}

198. HOUSE ROBBER (TABULATION)

int rob(vector<int>& nums) {

int n = [Link]();
if(n == 0) return 0;
if(n == 1) return nums[0];

vector<int> dp(n);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);

for(int i = 2; i < n; i++) {

int pick = nums[i] + dp[i - 2]; // Rob current house + value from i-2
int notpick = dp[i - 1]; // Skip current house
dp[i] = max(pick, notpick);
}

return dp[n - 1];

}

198. HOUSE ROBBER (TABULATION) (space optimised)

int rob(vector<int>& nums) {

int n = [Link]();
if(n == 0) return 0;
if(n == 1) return nums[0];

int a = nums[0]; // dp[i-2]

int b = max(nums[0], nums[1]); // dp[i-1]

for(int i = 2; i < n; i++) {

int pick = nums[i] + a;
int notpick = b;
int curr = max(pick, notpick);
a = b;
b = curr;
}

return b;
}

213. ROB HOUSE II

int help(vector<int>& nums) {

int n = [Link]();
if(n == 0) return 0;
if(n == 1) return nums[0];

vector<int> dp(n);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);

for(int i = 2; i < n; i++) {

 int pick = nums[i] + dp[i - 2]; // Rob current house + value from i-2
int notpick = dp[i - 1]; // Skip current house
dp[i] = max(pick, notpick);
}

return dp[n - 1];

}

int rob(vector<int>& nums){

int n = [Link]();
if(n == 0) return 0;
if(n == 1) return nums[0];

vector<int>temp1,temp2;
for(int i=0;i<n;i++){
if(i!=0) temp1.push_back(nums[i]);
if(i!=n-1) temp2.push_back(nums[i]);
}
int ans1=help(temp1);
int ans2=help(temp2);
return max(ans1,ans2);
}

NINJAS TRAINING ([Link]

leftPanelTabValue=PROBLEM) (MEMORISATION)

int f(int day, int act, vector<vector<int>> &points, vector<vector<int>> &dp){

if(day>=[Link]()){
return 0;
}
if(dp[day][act]!=-1){
return dp[day][act];
}
else{
int p=0;
int q=0;
int r=0;
if(act!=0){
p=points[day][0]+f(day+1,0,points,dp);
}
if(act!=1){
q=points[day][1]+f(day+1,1,points,dp);
}
if(act!=2){
r=points[day][2]+f(day+1,2,points,dp);
}
return dp[day][act]=max(p,max(q,r));
}
}
int ninjaTraining(int n, vector<vector<int>> &points)
{
// Write your code here.
vector<vector<int>> dp([Link](),vector<int>(3,-1));
int p=f(0,0,points,dp);
int q=f(0,1,points,dp);
int r=f(0,2,points,dp);

return max(p,max(q,r));
}
62. UNIQUE PATH (MEMORISATION)

int rec(pair<int,int> curr,pair<int,int> end,vector<vector<int>>& dp){

if(curr==end){
return 1;
}
if(dp[[Link]][[Link]]!=-1){
return dp[[Link]][[Link]];
}
int count=0;
if([Link]+1<=[Link]){
count+=rec({[Link]+1,[Link]},end,dp);
}
if([Link]+1<=[Link]){
count+=rec({[Link],[Link]+1},end,dp);
}
return dp[[Link]][[Link]]=count;

}
int uniquePaths(int m, int n) {
pair<int,int> start={0,0};
pair<int,int> end={m-1,n-1};
vector<vector<int>> dp(m,vector<int>(n,-1));
return rec(start,end,dp);
}

63. UNIQUE PATHS II (MEMORISATION)

int rec(pair<int,int> curr,pair<int,int> end,vector<vector<int>>& dp,

vector<vector<int>>& obstacleGrid){
if(curr==end){
return 1;
}
if(dp[[Link]][[Link]]!=-1){
return dp[[Link]][[Link]];
}
int count=0;
if([Link]+1<=[Link] and obstacleGrid[[Link]+1][[Link]]!=1){
count+=rec({[Link]+1,[Link]},end,dp,obstacleGrid);
}
if([Link]+1<=[Link] and obstacleGrid[[Link]][[Link]+1]!
=1){
count+=rec({[Link],[Link]+1},end,dp,obstacleGrid);
}
return dp[[Link]][[Link]]=count;

}
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {

pair<int,int> start={0,0};
int m=[Link]();
int n=obstacleGrid[0].size();
if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) {
return 0;
}
pair<int,int> end={m-1,n-1};
vector<vector<int>> dp(m,vector<int>(n,-1));
return rec(start,end,dp,obstacleGrid);
 }

64. MINIMUM PATH SUM (MEMORISATION)

int rec(pair<int,int> curr,pair<int,int> end,vector<vector<int>>&

grid,vector<vector<int>>& dp){
if(curr==end){
return grid[[Link]][[Link]];
}
if(dp[[Link]][[Link]]!=-1){
return dp[[Link]][[Link]];
}
int right=INT_MAX;
int down=INT_MAX;
if([Link]+1<=[Link]){
down=grid[[Link]][[Link]]
+rec({[Link]+1,[Link]},end,grid,dp);
}
if([Link]+1<=[Link]){
right=grid[[Link]][[Link]]
+rec({[Link],[Link]+1},end,grid,dp);
}
return dp[[Link]][[Link]]=min(down, right);
}
int minPathSum(vector<vector<int>>& grid) {
pair<int,int> start={0,0};
int m=[Link]();
int n=grid[0].size();
pair<int,int> end={m-1,n-1};
vector<vector<int>> dp(m,vector<int>(n,-1));
return rec(start,end,grid,dp);
}

120. TRIANGLE (MEMORISATION)

int rec(pair<int,int> curr,vector<vector<int>>& triangle,int

height,vector<vector<int>>& dp){
if([Link]==height-1){
return triangle[[Link]][[Link]];
}
if(dp[[Link]][[Link]]!=-1){
return dp[[Link]][[Link]];
}
int left=INT_MAX;
int right=INT_MAX;
left=triangle[[Link]][[Link]]
+rec({[Link]+1,[Link]},triangle,height,dp);
right=triangle[[Link]][[Link]]
+rec({[Link]+1,[Link]+1},triangle,height,dp);
return dp[[Link]][[Link]]=min(left,right);
}
int minimumTotal(vector<vector<int>>& triangle) {
int height=[Link]();
int base=triangle[height-1].size();
pair<int,int> start={0,0};
vector<vector<int>> dp;
for (int i = 0; i < height; ++i) {
dp.push_back(vector<int>(triangle[i].size(), -1));
}
 return rec(start,triangle,height,dp);

416. PARTITION EQUAL SUBSET SUM (TABULATION SOLN)

bool canPartition(vector<int>& nums) {

int sum = accumulate([Link](), [Link](), 0);
if (sum % 2 != 0) return false;

int target = sum / 2;

int n = [Link]();
vector<vector<bool>> dp(n+1, vector<bool>(target+1, false));

for (int i = 0; i <= n; i++) {

dp[i][0] = true; // base case: sum 0 is always possible
}

for (int i = n-1; i >= 0; i--) {

for (int t = 0; t <= target; t++) {
bool notPick = dp[i+1][t];
bool pick = (t - nums[i] >= 0) ? dp[i+1][t - nums[i]] : false;
dp[i][t] = pick || notPick;
}
}

return dp[0][target];
}

695. MAXIMUM AREA OF ISLAND

int maxAreaOfIsland(vector<vector<int>>& grid){

int m=[Link]();
int n=grid[0].size();
int res=0;
vector<vector<int>> vis(m,vector<int>(n,-1));
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j]==1 and vis[i][j]==-1){
int len=1;
queue<pair<int,int>> q;
[Link]({i,j});
vis[i][j]=1;
while(![Link]()){
auto [r,c]=[Link]();
[Link]();
for(auto [dr,dc]: dir){
int newr=r+dr;
int newc=c+dc;
if(newr<m and newr>=0 and newc<n and newc>=0){
if(grid[newr][newc]==1 and vis[newr][newc]==-1){
[Link]({newr,newc});
vis[newr][newc]=1;
len++;
}
}
}
}
res=max(res,len);
 }
}
}
return res;
}

322. COIN CHANGE (MEMORISATION SOLN)

int rec(vector<int>& coins, int amount, vector<int>& dp) {

if (amount == 0) return 0;
if (amount < 0) return INT_MAX;

if (dp[amount] != -1) return dp[amount];

int minCoins = INT_MAX;

for (int i = 0; i < [Link](); i++) {
int res = rec(coins, amount - coins[i], dp);
if (res != INT_MAX) {
minCoins = min(minCoins, res + 1);
}
}
return dp[amount] = minCoins;
}

int coinChange(vector<int>& coins, int amount) {

vector<int> dp(amount + 1, -1);
int res = rec(coins, amount, dp);
return (res == INT_MAX) ? -1 : res;
}

322. COIN CHANGE (TABULATION SOLN)

int coinChange(vector<int>& coins,int amount){

vector<int> dp(amount+1,INT_MAX);
dp[0]=0;
for(int i=1;i<=amount;i++){
for(auto coin: coins){
if(i-coin>=0 and dp[i-coin]!=INT_MAX){
dp[i]=min(dp[i],dp[i-coin]+1);
}
}
}
return dp[amount]==INT_MAX ? -1:dp[amount];
}

2915. LENGTH OF LONGEST SUBSEQUENCE THAT SUMS TO TARGET (MEMORISATION SOLUTION)

int rec(vector<int>& nums, int target, int index,vector<vector<int>>& dp) {

if (target == 0) return 0;
if (index == [Link]() || target < 0) return INT_MIN;

if(dp[target][index]!=-1){
return dp[target][index];
}

// Choice 1: Include nums[index]

int take = rec(nums, target - nums[index], index + 1,dp);
if (take != INT_MIN) take += 1;
 // Choice 2: Skip nums[index]
int skip = rec(nums, target, index + 1,dp);

return dp[target][index]=max(take, skip);

}

int lengthOfLongestSubsequence(vector<int>& nums, int target) {

vector<vector<int>> dp(target+1,vector<int>([Link](),-1));
int res = rec(nums, target, 0,dp);
return (res == INT_MIN) ? -1 : res;
}

LONGEST COMMON SUBSTRING

int longestCommonSubstr(string& text1, string& text2){

int m=[Link]();
int n=[Link]();
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
int ans=0;
for(int i=m-1;i>=0;i--){
for(int j=n-1;j>=0;j--){
if(text1[i]==text2[j]){
dp[i][j]=1+dp[i+1][j+1];
ans=max(ans,dp[i][j]);
}
else{
dp[i][j]=0;
}
}
}

return ans;
}

139. WORD BREAK

bool wordBreak(string s, vector<string>& wordDict) {

int n=[Link]();
vector<bool> dp(n+1,false);
dp[n]=true;
for(int i=[Link]()-1;i>=0;i--){
for(auto& x: wordDict){
int len=[Link]();
if(i+len <=n and x==[Link](i,len)){
dp[i]=dp[i+len];
if (dp[i]) break;
}
}
}
return dp[0];
}