一个商人穿过一个N×N的正方形的网格,去参加一个非常重要的商务活动.他要从网格的左上角进,右下角出.每穿越中间1个小方格,都要花费1个单位时间.商人必须在(2N-1)个单位时间穿越出去.而在经过中间的每个小方格时,都需要缴纳一定的费用.
这个商人期望在规定时间内用最少费用穿越出去.请问至少需要多少费用?
注意:不能对角穿越各个小方格(即,只能向上下左右四个方向移动且不能离开网格).
输入格式:
第一行是一个整数,表示正方形的宽度N (1≤N<100);
后面N行,每行N个不大于100的整数,为网格上每个小方格的费用.
注意题目条件:1,商人必须在(2N-1)个单位时间穿越出去.2,不能对角穿越各个小方格(即,只能向上下左右四个方向移动且不能离开网格).分析可知,商人只能往右或者往下移动.创建一个二维数组m[i][j]记录从上一个位置到该位置的最小花费,那么最后m[n][n]的值就是答案.
因为是二重循环所以时间复杂度是O(n^2)
因为开辟了一个二维数组m[i][j]所以空间复杂度是O(n^2)
分析问题时要耐心找到解决题目的递归方程式,再细心处理边界问题,问题就能迎刃而解.
动态规划思想和上一章的分治法类似,都是将问题分解为多个子问题,通过求解子问题来得到最终答案,而动态规划的优势在于,动态规划防止了子问题的重复计算,每个问题只计算一次,自底向上地求出原问题的解,这样可以提高运行的效率,帮助我们更好地解决问题.