KEMBAR78
DP Pattern | PDF
Scribd
Upload
21 views2 pages

DP Pattern

The document contains two classes implementing dynamic programming solutions for specific problems. The first class finds the length of the longest subsequence that sums to a target using a memoization approach, while the second class computes the minimum path sum in a grid. It also suggests using 1e9 instead of INT_MAX to avoid integer overflow issues.

Uploaded by

Yash Mathuria
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
21 views2 pages

DP Pattern

The document contains two classes implementing dynamic programming solutions for specific problems. The first class finds the length of the longest subsequence that sums to a target using a memoization approach, while the second class computes the minimum path sum in a grid. It also suggests using 1e9 instead of INT_MAX to avoid integer overflow issues.

Uploaded by

Yash Mathuria
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 2

1.

Target sum using dp memo pattern

class Solution {

public:

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

if (target == 0) return 0;

if (index < 0&& target!=0) return INT_MIN;

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

// Option 1: Don't take the current number

int notTake = helper(nums, index - 1, target, dp);

// Option 2: Take the current number (if it fits)

int take = INT_MIN;

if (nums[index] <= target) {

int res = helper(nums, index - 1, target - nums[index], dp);

if (res != INT_MIN) take = 1 + res;

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

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

int n = nums.size();

vector<vector<int>> dp(n, vector<int>(target + 1, -1));

int ans=helper(nums, n - 1, target, dp);

return (ans<0)?-1:ans;

};
[2] DP On Grid

class Solution {
public:
int n;
int m;
vector<vector<int>>dp;
int helper(vector<vector<int>>&grid,int row,int col ){
if(row==n-1&&col==m-1){
return grid[n-1][m-1];
}
if(row>=n||col>=m){
return INT_MAX;
}
if(dp[row][col]!=-1){
return dp[row][col];
}
int right=helper(grid,row,col+1);
int down=helper(grid,row+1,col);
return dp[row][col]=min(right,down)+grid[row][col];
}
int minPathSum(vector<vector<int>>& grid) {
n=grid.size();
m=grid[0].size();
dp.assign(n+1,vector<int>(m+1,-1));
return helper(grid,0,0);
}
};
1. Base case
2. 2. Recursive logic than
3. Return statement that you want ans

It’s better to use 1e9 instead of INT_MAX because of integer overflow issue in this question
when we try to add grid[i][j] with right and down it will give error but if we return 1e9 than it will
easily pass

You might also like