走两次的方格取数问题 - 基础入门+刷题小组 - 美国米群网 － 海外华人留学生最大面试求职社交平台 － 计算机 商科 面试 面经 内推 刷题 算法 职场 绿卡 家庭 休闲 - Powered by MeetQun!
以上代码的复杂度空间复杂度是O(n^3)，稍微想一下可以知道我们在推算dp[step]的时候 只有到了dp[step - 1]，所以第一维，我们只开到2就可以了。就是step为奇数时，我们都用dp[1][j]表示状态，step为偶数我们都用dp[0][j]表示状态，这样我们只需要O(n^2)的空间，这就是滚动数组的方法。滚动数组写起来并不复杂，只需要对上面的代码稍作修改即可
Read full article from 走两次的方格取数问题 - 基础入门+刷题小组 - 美国米群网 － 海外华人留学生最大面试求职社交平台 － 计算机 商科 面试 面经 内推 刷题 算法 职场 绿卡 家庭 休闲 - Powered by MeetQun!
问题 给定n行n列的方阵，每个元素是一个整数，从左上角走到右下角，每次只能向右或者下，走两次，使得得到的总和最大。同一次经过两个元素的话，总和只计算一次。
分析： 如果是只走一次的话，是经典的dp。走两次的话，dp两次是不对的……因为状态之间有影响，第一次和最大的路径可能会影响第二次的路径。这个题还有一个变形，是等价的，就是说从起点到终点只能向右和下，再从终点回起点只能向上或者左，使得总和最大。
搜索是指数的算法，贪心不靠谱，两次dp也不行。所以还是尝试两个人同时走……，有个好处是，两个人一起走的话，只能在同一步经过相同的格子，这是由距离决定的。因为第step步，所在的格子距离起点的曼哈顿距离|x - x' | + |y - y'| = step……所以走一次时，状态是dp[(x,y)]由(x - 1, y) (x, y - 1)决定，现在状态是dp[(x1,y1)(x2,y2)]由4个状态确定即dp[(x1 - 1, y1)(x2 - 1, y2)] dp[(x1 - 1, x2, y2 - 1)] dp[(x1, y1 - 1)(x2 - 1, y2)] dp[(x1, y1 - 1) (x2 , y2 - 1)]确定。
以上代码的复杂度空间复杂度是O(n^3)，稍微想一下可以知道我们在推算dp[step]的时候 只有到了dp[step - 1]，所以第一维，我们只开到2就可以了。就是step为奇数时，我们都用dp[1][j]表示状态，step为偶数我们都用dp[0][j]表示状态，这样我们只需要O(n^2)的空间，这就是滚动数组的方法。滚动数组写起来并不复杂，只需要对上面的代码稍作修改即可
Read full article from 走两次的方格取数问题 - 基础入门+刷题小组 - 美国米群网 － 海外华人留学生最大面试求职社交平台 － 计算机 商科 面试 面经 内推 刷题 算法 职场 绿卡 家庭 休闲 - Powered by MeetQun!
