70.
CLIMBING STAIRS (RECURSSIVE)
https://leetcode.com/problems/climbing-stairs/description/
int climbStairs(int n) {
if(n==0 or n==1){
return 1;
}
return climbStairs(n-1)+climbStairs(n-2);
}
70. CLIMBING STAIRS (memoisation)
https://leetcode.com/problems/climbing-stairs/description/
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)
https://leetcode.com/problems/climbing-stairs/description/
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 (m.find(state) != m.end()) {
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 (stones.size() < 2 || stones[1] != 1) return false;
set<int> stone_set(stones.begin(), stones.end());
int last_stone = stones.back();
return dfs(1, 1, stone_set, last_stone);
}
198. HOUSE ROBBER (MEMORISATION)
int rec(int curr,vector<int>& nums,vector<int> &s){
if(curr>=nums.size()){
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(nums.size()+1,-1);
return rec(0,nums,s);
}
198. HOUSE ROBBER (TABULATION)
int rob(vector<int>& nums) {
int n = nums.size();
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 = nums.size();
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 = nums.size();
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 = nums.size();
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 (https://www.naukri.com/code360/problems/ninja-s-training_3621003?
leftPanelTabValue=PROBLEM) (MEMORISATION)
int f(int day, int act, vector<vector<int>> &points, vector<vector<int>> &dp){
if(day>=points.size()){
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(points.size(),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[curr.first][curr.second]!=-1){
return dp[curr.first][curr.second];
}
int count=0;
if(curr.first+1<=end.first){
count+=rec({curr.first+1,curr.second},end,dp);
}
if(curr.second+1<=end.second){
count+=rec({curr.first,curr.second+1},end,dp);
}
return dp[curr.first][curr.second]=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[curr.first][curr.second]!=-1){
return dp[curr.first][curr.second];
}
int count=0;
if(curr.first+1<=end.first and obstacleGrid[curr.first+1][curr.second]!=1){
count+=rec({curr.first+1,curr.second},end,dp,obstacleGrid);
}
if(curr.second+1<=end.second and obstacleGrid[curr.first][curr.second+1]!
=1){
count+=rec({curr.first,curr.second+1},end,dp,obstacleGrid);
}
return dp[curr.first][curr.second]=count;
}
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
pair<int,int> start={0,0};
int m=obstacleGrid.size();
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[curr.first][curr.second];
}
if(dp[curr.first][curr.second]!=-1){
return dp[curr.first][curr.second];
}
int right=INT_MAX;
int down=INT_MAX;
if(curr.first+1<=end.first){
down=grid[curr.first][curr.second]
+rec({curr.first+1,curr.second},end,grid,dp);
}
if(curr.second+1<=end.second){
right=grid[curr.first][curr.second]
+rec({curr.first,curr.second+1},end,grid,dp);
}
return dp[curr.first][curr.second]=min(down, right);
}
int minPathSum(vector<vector<int>>& grid) {
pair<int,int> start={0,0};
int m=grid.size();
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(curr.first==height-1){
return triangle[curr.first][curr.second];
}
if(dp[curr.first][curr.second]!=-1){
return dp[curr.first][curr.second];
}
int left=INT_MAX;
int right=INT_MAX;
left=triangle[curr.first][curr.second]
+rec({curr.first+1,curr.second},triangle,height,dp);
right=triangle[curr.first][curr.second]
+rec({curr.first+1,curr.second+1},triangle,height,dp);
return dp[curr.first][curr.second]=min(left,right);
}
int minimumTotal(vector<vector<int>>& triangle) {
int height=triangle.size();
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(nums.begin(), nums.end(), 0);
if (sum % 2 != 0) return false;
int target = sum / 2;
int n = nums.size();
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=grid.size();
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;
q.push({i,j});
vis[i][j]=1;
while(!q.empty()){
auto [r,c]=q.front();
q.pop();
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){
q.push({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 < coins.size(); 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 == nums.size() || 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>(nums.size(),-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=text1.size();
int n=text2.size();
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=s.size();
vector<bool> dp(n+1,false);
dp[n]=true;
for(int i=s.size()-1;i>=0;i--){
for(auto& x: wordDict){
int len=x.size();
if(i+len <=n and x==s.substr(i,len)){
dp[i]=dp[i+len];
if (dp[i]) break;
}
}
}
return dp[0];
}
