leadcode的Hot100系列--64. 最小路径和--权值最小的动态规划

如果这个：
leadcode的hot100系列--62. 不同路径--简单的动态规划

看懂的话，那这题基本上是一样的，
不同点在于：
1、这里每条路径相当于多了一个权值
2、结论不再固定，而是要比较不同走法哪个权值更小

针对第一点，需要把第一行和第一列的权值做一个累加：
假设这里的权值都是1，则

a	b	c	d
e	f	g	h
i	j	k	l

中，f(a) 为1，f(b) 就为2,，因为a和b各有一个权值，f(c)为3，f(e) 为2，f(i)为3：

1	2	3	4
2	f(f)	f(g)	f(h)
3	f(j)	f(k)	f( l)

要想 f(f) 小，则要比较f(b)和f(e)哪个小，所以 f(f) = min( f(f), f(e) ) + 1。
所以很容易得到动态方程：

f [i] [j] = min( f [i] [j-1] + f [i-1] [j] ) + 1 // i 代表行，j 代表列，最后加的1，是假设当前的点的权值是1

所以，每个点记录的从开始到当前点的最小值。

int min(int a, int b)
{
    return a<b?a:b;
}

int minpathsum(int** grid, int gridsize, int* gridcolsize){
    int p[gridsize][*gridcolsize];
    int sum = 0, i,j;
    
    for (i=0; i<gridsize; i++)    // 先算出第一列的权值
    {
        sum += grid[i][0];
        p[i][0] = sum;
    }
    sum = 0;
    for (i=0; i<*gridcolsize; i++)    // 先算出第一行的权值
    {
        sum += grid[0][i];
        p[0][i] = sum;
    }
    
    for (i=1; i<gridsize; i++)
    {
        for (j=1; j<*gridcolsize; j++)
        {
            p[i][j] = min(p[i][j-1], p[i-1][j]) + grid[i][j];    //  动态方程
        }
    }
    return p[gridsize-1][*gridcolsize-1];
}