// For each position i, it evaluates all possible previous positions within
//the jump limit k and updates the cost based on the minimum difference in values.
int minimizeCost(vector<int>& arr, int& k) {
int n = arr.size();
vector<int>dp(n,-1);
dp[0] = 0;
int res=0;
for(int i=1;i<n;i++){
int minVal = INT_MAX;
for(int j=1;j<=k;j++){
if(i-j>=0){
int ans = dp[i-j]+abs(arr[i]-arr[i-j]);
minVal = min(ans,minVal);
}
}
dp[i]=minVal;
}
return dp[n-1];
}
int rob(vector<int>& nums) {
int n = nums.size();
int prev2=0, prev= nums[0];
for(int i=1;i<n;i++){
int take = prev2+nums[i];
int notTake = prev + 0;
int curr = max(take, notTake);
prev2=prev;
prev=curr;
}
return prev;
}
If in above problem instead of array we have circular array such that first house and last house cannot be robbed together then we can find max of nums([0:n-1]),nums([1:n])
int uniquePaths(int m, int n) {
vector<int>prev(m,1);
for(int i=1;i<n;i++){
vector<int> temp(m,1);
for(int j=1;j<m;j++){
temp[j]= prev[j]+temp[j-1];
}
prev=temp;
}
return prev[m-1];
}
Given an array of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.
bool isSubsetSum(vector<int>arr, int sum){
vector<bool>prev(sum+1,false);
prev[0] = true;
int n= arr.size();
if(arr[0]<=sum){
prev[arr[0]] = true;
}
for(int i=1;i<n;i++){
vector<bool> curr(sum+1,false);
curr[0] = true;
for(int j=1;j<=sum;j++){
bool notTake = prev[j];
bool take = false;
if(arr[i]<=j){
take = prev[j-arr[i]];
}
curr[j] = take|| notTake;
}
prev = curr;
}
return prev[sum];
}
Given an array arr of size n of non-negative integers and an integer sum, the task is to count all subsets of the given array with a sum equal to a given sum.
int perfectSum(int arr[], int n, int sum)
{ int mod = 1e9+7;
vector<long long>prev(sum+1,0);
prev[0]=1;
if(sum>=arr[0]){
prev[arr[0]]=1;
}
for(int i=1;i<n;i++){
vector<long long>curr(sum+1,0);
curr[0]=1;
for(int target =1 ;target<=sum;target++){
long long notTaken = prev[target]%mod;
long long taken=0;
if(target>=arr[i]){
taken = prev[target-arr[i]]%mod;
}
curr[target]=(taken+notTaken)%mod;
}
prev= curr;
}
return prev[sum];
}
int maxProduct(vector<int>& nums) {
int mxP = INT_MIN;
int prefix=1;
int suffix=1;
int n= nums.size();
for(int i=0;i<n;i++){
if(prefix==0){
prefix=1;
}
if(suffix==0){
suffix=1;
}
prefix=prefix*nums[i];
suffix=suffix*nums[n-i-1];
mxP=max(mxP, max(prefix,suffix));
}
return mxP;
}
}