how dynamic programming works

Posted on |

leetcode 64(Mini Path Sum): 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.

the first thought is to build a tree：

     1
     /        \
  1       3 
 / \     / \
4   5   1   5
/  /\   /   /\
2  1 2  1   1 2

while this is not a balanced tree, no regular tree way to maintain. Then what else solution? Dynamic Programming is a strategy to solve a simple problem at first, then find the rules(status transfer from previous state to current state) for the remaining problems.

step1: the simpler problem, or as initial/boundary condition. e.g. only one row, or only one col, what’s the solution.

step2: in general m rows, n cols, how to get the iterative rules after step1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
int sol(vector<vector<int> >& mat)
{
	vector<vector<int> > dp; 
	
	int row = mat.size();
	int col = mat[0].size(); 
	
	for(int i=0; i<row; i++)
		dp[i][0] += mat[i][0];
    for(int j=0; j<col; j++)
		dp[0][j] += mat[0][j];
	
	for(int i=1; i<row; i++)
		for(int j=1; j<col; j++)
			dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + mat[i][j]; 
	
	return dp[row-1][col-1]; 
}
int main()
{
 vector<int> v1, v2, v3 ;
 v1 = {1, 3, 1};
 v2 = {1, 5, 1};
 v3 = {4, 2, 1}
 
 vector<vector<int> >   mat;
 mat.push_back(v1);
 mat.push_back(v2);
 mat.push_back(v3);
 
 int out = sol(mat);
 
 cout << "output =" << out << endl; 
 
 return 0;
}

See DP solution is much clear than design the tree.