k922,linux mint,咖啡馆标价三十结账九百
如果这个:
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]; }
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论