minCostPath.cpp

#include <iostream>
#include <algorithm>

using namespace std;

int main(){
	std::ios::sync_with_stdio(false);
	/*
		We can easily observe that the optimum solution of the minimum
		cost at any row i is only dependent on the cost at row i-1 and
		the current row elements. Thus if we only store these two arrays
		of length c, We have reduced space from n*m to 2*m.
	*/

	int i, j, r, c;
  printf("Enter no of rows and no of cols\n");
	cin>>r>>c;     //take input of the rows and columns from user.
	int cost[c], dp[c];
	int x;
	/*
		Since for the first row the minimum cost is the only cost possible
		required to get there, we directly calculate it.
	*/
  printf("Enter a R X C array\n");

	for(i=0; i<c; i++){
		cin>>cost[i];
		if(i>0) cost[i] = cost[i] + cost[i-1];
	}
	/*
		For the subsequent rows, the optimised cost for each cell in the
		previous row has been stored in the array cost[] and the optimised
		cost for the present row is stored in the array dp[].
	*/
	for(i=1; i<r; i++){
		for(j=0; j<c; j++){
			cin>>x;
			if(j==0)
				dp[j] = cost[j] + x;
			else{
				dp[j] = x + min(dp[j-1], min(cost[j-1], cost[j]));
			}
		}
		/*
			After dp[] has been found entirely, we copy its elements to
			cost[] and continue the iteration.
		*/
		for(j=0; (j<c && i!=c-1); j++){
			cost[j] = dp[j];
		}
	}
  printf("The min cost path from 1,1 to r,c is\n");
	cout<<dp[c-1]<<"\n";
	return 0;
}