# Min Cost Path-dynamic programming

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

example:

n=3,m=3;

a=[

[1,3,1],

[1,5,1],

[4,2,1]

]

**Output: 7**

Explanation: Because the path 1→3→1→1→1 minimizes the sum.

lets use dynamic programming to solve this question:

c++ implementation:

t is the no.of test cases:

**#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main() { int t; cin>>t;
while(t--)
{
int n; cin>>n;
int m;cin>>m;
int a[n][m];
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>a[i][j];
if (m == 0||n==0) return 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i > 0 && j > 0) {
a[i][j] += min(a[i - 1][j], a[i][j - 1]);
} else if (i > 0) {
a[i][j] += a[i - 1][j];
} else if (j > 0) {
a[i][j] += a[i][j - 1];
}
}
}
cout<< a[n - 1][m - 1];
cout<<endl;
}
//code
return 0;
}**