how dynamic programming works

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.