jain12

minimum cost path by Dynamic programming

Apr 29th, 2020
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.12 KB | None | 0 0
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. //first method
  5. int MinCost(int C[][3],int r,int c){
  6. int MC[r+1][c+1]={0,0};
  7. MC[0][0]=C[0][0];
  8. for(int i=0;i<=r;i++){
  9. for(int j=0;j<=c;j++){
  10. if(MC[i][j]==0){
  11. int first,second,third;
  12. first=(i-1>=0)? MC[i-1][j]:INT_MAX;
  13. second=(j-1>=0)? MC[i][j-1]:INT_MAX;
  14. third=(i-1>=0 && j-1 >=0)? MC[i-1][j-1]:INT_MAX;
  15. MC[i][j]=C[i][j]+min(first,min(second,third));
  16. }
  17. }
  18. }
  19. return MC[r][c];
  20. }
  21.  
  22. //second method from geeks for geeks
  23. int MinCost(int C[][3],int r,int c){
  24. int MC[r+1][c+1];
  25. MC[0][0]=C[0][0];
  26. for(int i=1;i<=r;i++)
  27. MC[i][0]=MC[i-1][0]+C[i][0];
  28. for(int i=1;i<=c;i++)
  29. MC[0][i]=MC[0][i-1]+C[0][i];
  30. for(int i=1;i<=r;i++){
  31. for(int j=1;j<=c;j++){
  32. MC[i][j]=min(MC[i-1][j-1], min(MC[i-1][j],MC[i][j-1]))+C[i][j];
  33. }
  34. }
  35. return MC[r][c];
  36. }
  37.  
  38. int main(){
  39. int r=3,c=3;
  40. int C[r][3]={ {1,2,3},
  41. {4,8,2},
  42. {1,5,3}
  43. };
  44. cout<<MinCost(C,2,2);
  45. return 0;
  46. }
Add Comment
Please, Sign In to add comment