CODEWITHSUNDEEP
pythonc++algorithmdata-structuresdynamic-programming
Tavish Jain
Tavish Jain

Reputation: 155

Finding minimum cost to reach the end of array

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?

Upvotes: 4

Views: 13807

Answers (11)

akash777.sharma
akash777.sharma

Reputation: 702

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;
}

Upvotes: 0

siddhant sajwan
siddhant sajwan

Reputation: 22

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;
}

Upvotes: 0

Niharika Sahai
Niharika Sahai

Reputation: 1

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;

Upvotes: -1

user3771709
user3771709

Reputation: 49

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]));

}

}

Upvotes: 0

Abhishek verma
Abhishek verma

Reputation: 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);
    }

Upvotes: 0

Shuchita Banthia
Shuchita Banthia

Reputation: 308

DP based solution - Fill up 1-D cost array in bottom up manner. Involves 2 steps:

  1. On reaching index i, check and update cost if we it can be improved by arriving on it from index i+1.
  2. Update the cost of reaching element at i+2.

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]))

Upvotes: 2

Gaurav Sohaliya
Gaurav Sohaliya

Reputation: 1

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;
}

Upvotes: -1

samsri
samsri

Reputation: 1104

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))

Upvotes: 1

Ritik Jain RJ
Ritik Jain RJ

Reputation: 9

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];
}

Upvotes: 0

Arjun U S
Arjun U S

Reputation: 199

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];
}

Upvotes: 3

Yash Shah
Yash Shah

Reputation: 1654

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).

Upvotes: 3

Related Questions