作为一个拖延症懒癌患者，外加年久失修，基础不牢，我决定每天做一题，坚持打卡，今天是我第一天，希望自己可以坚持下来。
Given amxn grid filled with non-negative numbers, find a path from top left to bottom right whichminimizesthe sum of all numbers along its path.
Note:You can only move either down or right at any point in time.
题目大意大致为有这样一个数组，数组里都有对应的值，可以向下走或者向右走，最后返回数值最小的路径，可以理解为一个动态规划的问题。
动态规划：（这是第一次做动态规划方面的题目，也不想搞ACM竞赛之类，只是想积累经验）
摘自知乎 作者：端泽
先谈动态规划的意义——望文生义，“动态”规划对应“动态”的问题：你并不知道问题的规模会有多大，而不论是个位数还是百万级，都能以较快速度(动态规划是一种泛用性算法，而泛用性算法与特定算法相比往往存在性能差距)将结果正确计算出来。这是对于计算机科学最直观的意义，当然我认为其对人生亦有一定指导意义，但那是见仁见智的事了。
动态规划这一思想的实质其实是以下两点：
1.分析问题，构造状态转移方程
2.以空间换时间
让我们结合一个简单例子来理解一下：
以乘法计算为例，乘法的定义其实是做n次加法，请先忘掉九九乘法表，让你计算9*9，如何得到81这个解？计算9*10呢？9*999……以及9*n呢？
1.分析问题，构造状态转移方程
“状态转移方程”的学术定义亦可简单找到（比如置顶答案），略去不表。光看“方程”二字，可以明白它是一个式子。
针对以上问题，我们构造它的状态转移方程。
问题规模小的时候，我们可以容易得到以下式子：
9*0=0；
9*1=0+9；
9*2=0+9+9；
……
可以得到：9*n=0+9+...+9(总共加了n个9)。严谨的证明可以使用数学归纳法，略去不表。
现在，定义dp(n)=9*n,改写以上式子：
dp(0)=9*0=0；
dp(1)=9*1=dp(0)+9；
dp(2)=9*2=dp(1)+9；
……
作差易得：dp(n)=dp(n-1)+9；这就是状态转移方程了。
可以看到，有了状态转移方程，我们现在可以顺利求解9*n（n为任意正整数）这一问题。
2.以空间换时间
虽然能解，但当n很大时，计算耗时过大，看不出状态转移方程dp(n)=dp(n-1)+9与普通方程9*n=0+9+...+9(总共加了n个9)相比没有任何优势。
这时，如果dp(n-1)的结果已知，dp(n)=dp(n-1)+9只需计算一次加法，而9*n=0+9+...+9(总共加了n个9)则需计算n-1次加法，效率差异一望即知。
存储计算结果，可令状态转移方程加速，而对普通方程没有意义。
以空间换时间，是令动态规划具有实用价值的必备举措。
总之，根据我的理解，我觉得这个很像小时候做的找规律的题目，第n个数需要靠之前的来得到，因此，叫做动态规划，也就是dp。
接下来要看这道题了，假如我有一个矩阵grid：
1 2 3 4
5 9 9 0
1 8 4 3
我得到一个新的矩阵，result记录着gird里面到达每一个元素的最小值，这样最后一个元素也就是我们所要求的值，就是到他的最小值，因此，
result[0][0] = gird[0][0]
result[0][j] = result[0][j-1]+gird[0][j]
result[i][0] = result[]i-1[0]+gird[i][0]
result[i][j] = min(result[i - 1][j], result[i][j - 1])+gird[i][j]
接下来就是算法的实现了：
结束......
joker
网友评论