An array of costs was given. You can either take two jumps forward or one jump backward. If you land on a particular index, you have to add the cost to your total. Find the minimum cost needed to cross the array or reach the end of the array.
Input:
5 (Number of elements in the array)
[9,4,6,8,5] (Array)
1 (Index to start)
Output:
12
Explanation: We start from index 1, jump to 3 and then jump out for a total cost of 8+4=12.
How can we build the DP solution for this?
You can use Dijkstra's algorithm(graph) for solving this problem.
Follow these steps:
1. Generate Weighted directed graph by connecting a node of ith index with nodes at (i-1)th and (i+2)th index with their cost(if possible).
2. Apply Dijkstra's algorithm to find the shortest route between the initial node(index) and the target node(index).
You can use recursive program with Dp
//cur will the final destination that is last element at first execution
//N is no of elements
int Dp[N]={0};
Dp[0]=element[0]; //initial condition
least_path(cur,*elements,N)
{
if(cur>N-1 || cur<0)
return INT_MAX;
if(Dp[cur])
return Dp[cur];
int temp1=least_path(cur-2,*elements,N)+element[cur];
int temp2=least_path(cur+1,*elements,N)+element[cur];
Dp[cur]=min(temp1,temp2);
return Dp[cur];
}
DP based solution - Fill up 1-D cost array in bottom up manner. Involves 2 steps:
Time complexity: O(n), where n is length of input array.
# Python3 snippet
# Inputs: startIndex, array A of non negative integers
# Below snippet assumes A has min length 3 beginning from the startIndex. We can handle smaller arrays with base cases - thus, not listing them out explicitly
import math
costs = [math.inf] * len(A)
costs[startIndex] = A[startIndex]
costs[startIndex+1] = A[startIndex] + A[startIndex+1] + min(A[startIndex+1], A[startIndex-1] if startIndex >=0 else A[startIndex+1])
N = len(A)
for i in range(startIndex, N):
if i+1 < N:
costs[i] = min(costs[i], costs[i+1] + A[i])
if i + 2 < N:
costs[i+2] = costs[i] + A[i+2]
print(min(costs[-1], costs[-2]))
I've used path to represent all the visited nodes visited so far
res to represent the result so far
import sys
infi = sys.maxsize
def optimum_jump_recurse(arr, curr_pos, cost, path, res):
if curr_pos in path or cost > res or curr_pos < 0:
return infi
elif curr_pos > len(arr) - 1:
if cost < res:
res = cost
return cost
res = optimum_jump_recurse(arr, curr_pos + 2, cost + arr[curr_pos],
path | {curr_pos}, res)
backward_cost = optimum_jump_recurse(arr, curr_pos - 1,
cost + arr[curr_pos],
path | {curr_pos}, res)
if res == backward_cost == infi:
return res
res = min(res, backward_cost)
actual_cost = res - cost
return res
nums = [1, 2, 3, 4, 100]
# nums = [1, 2, 3]
# nums = [1]
# nums = [1, 2]
# nums = [1, 2, 3, 100, 200]
# nums = [1, 1000, 3, 100, 200]
# nums = [1, 1, 3, 100, 200]
# nums = [1, 1, 3, 5, 100, 200]
# nums = [1, 2, 3, 100, 4]
def optimum_jump(nums):
return optimum_jump_recurse(nums, 0, 0, set(), infi)
print(optimum_jump(nums))
C++ solution (dijikstras)
int minDist(vector<bool> &visited, vector<int> &dist, int n){
int m = INT_MAX, res = 0;
for(int i = 0; i < n; i++)
if(!visited[i] && m > dist[i])
m = dist[i], res = i;
return res;
}
int minJump(int *arr, int n){
vector<bool> visited(n, false);
vector<int> dist(n, INT_MAX);
dist[0] = 0;
for(int c = 0; c < n - 1; c++){
int u = minDist(visited, dist, n);
visited[u] = true;
if(u + 2 < n && !visited[u + 2] && dist[u] + arr[u + 2] < dist[u + 2])
dist[u + 2] = dist[u] + arr[u + 2];
if(u - 1 >= 0 && !visited[u - 1] && dist[u] + arr[u - 1] < dist[u - 1])
dist[u - 1] = dist[u] + arr[u - 1];
}
return dist[n - 1];
}
Following code would work to get min cost for index 0 to N-1
int[] dp;
boolean[] visited;
int func(int pos, int N, int[] cost){
if(pos == 0) return 0;
if(dp[pos] != -1) return dp[pos];
visited[pos] = true;
int dist = Integer.MAX_VALUE;
if(pos-2 > -1 && !visited[pos-2]) dist = Math.min(dist, cost[pos-2] + func(pos-2,N,cost));
if(pos+1 < N && !visited[pos+1]) dist = Math.min(dist, cost[pos+1] + func(pos+1,N,cost));
return dp[pos] = dist;
}
int min_cost_to_reach_the_end(int[] cost){
int N = cost.length;
this.dp = new int[N];
this.visited = new boolean[N];
Arrays.fill(dp,-1);
return func(N-1, N, cost);
}
I know it's late but please check this.
public class MinimumCost {
public static void main(String ar[]){
int arr[]={9,4,6,8,5};
int startIndex=1;
int DP[]=new int[arr.length];
for(int i=0;i<arr.length;i++){
DP[i]=100000;//I just take this as maximum value .you can change it.
}
DP[startIndex] = arr[startIndex] ;
DP[startIndex+2] = arr[startIndex] + arr[startIndex+2] + Math.min(arr[startIndex+2], arr[startIndex]);
int n=arr.length;
for(int i=0;i<n-1;i++){
if ((i+1)<n)
DP[i] = Math.min(DP[i], (DP[i+1]) + arr[i]);
if ((i + 2 )< n)
DP[i+2] = DP[i] + arr[i+2];
}
System.out.println(Math.min(DP[arr.length-1],DP[arr.length-2]));
}
}
function solve(A_i) {
A_i.sort((a,b) => a-b);
let totalcost = A_i[0];
for(let i=2; i<A_i.length;i++) {
if(i + 1 == A_i.length -1) {
totalcost = totalcost + A_i[i];
break;
}
const preSum = A_i[i] + A_i[i+2];
const postSum = A_i[i] + A_i[i-1] + A_i[i+1];
if(preSum <= postSum) {
totalcost = totalcost + A_i[i];
i++;
} else {
totalcost = totalcost + A_i[i];
i = i-2;
console.log(i)
}
}
return totalcost;
}
solution in java using DP (iterative solution), constant memory and linear time complexity
long getJumpCost(int arr[]) {
int length = arr.length;
long dp[] = new long[length];
for(int i=0; i<length; i++) {
dp[i] = Long.MAX_VALUE;
}
dp[0] = arr[0];
dp[2] = dp[0] + (long)arr[2];
dp[1] = dp[2] + (long)arr[1];
for(int i=3; i<length; i++) {
dp[i] = Math.min(dp[i], dp[i-2] + (long)arr[i]);
dp[i-1] = Math.min(dp[i-1], dp[i] + (long)arr[i-1]);
}
long result = Math.min( dp[length-1], dp[length-2]);
return result;
}
You can use the following code:
#include <iostream>
using namespace std;
int main()
{
int n=3;
bool flag = true;
while(n)
{
//take last two bits then right shift
int i = n%2;
n=n/2;
int j = n%2;
n=n/2;
//check with given pattern 01 & 10 is allowed only
if((i==0 && j==1) || (i==1 && j==0))
{
//right pattern
}
else{
//not allowed
flag = false;
break;
}
}
if(flag)
cout<<"YES";
else
cout<<"NO";
return 0;
}
JAVA Solution: The solution takes O(n2)
int minCost[] = new int[N];
Arrays.fill(minCost,Integer.MAX_VALUE);
for(int i=0;i<A.length;i++){
for(int j=0;j<A.length;j++){
if(j == 0){
minCost[j] = 0;
continue;
}
if(j-2>=0 && minCost[j-2]!=Integer.MAX_VALUE){
minCost[j] = Math.min(minCost[j-2]+A[j-2],minCost[j]);
}
if(j+1<A.length && minCost[j+1]!=Integer.MAX_VALUE){
minCost[j] = Math.min(minCost[j+1]+A[j+1],minCost[j]);
}
}
}
if(minCost[A.length-2]!= Integer.MAX_VALUE && minCost[A.length-1]!= Integer.MAX_VALUE){
return Math.min(A[A.length-2]+minCost[A.length-2],minCost[A.length-1]+A[A.length-1]);
}
if(minCost[A.length-2]!= Integer.MAX_VALUE){
return minCost[A.length-1]+A[A.length-1];
}
if(minCost[A.length-1]!= Integer.MAX_VALUE){
return A[A.length-2]+minCost[A.length-2];
}
return -1;