题目
一个3✖️n的二维数组，找到从第一列到最后一列的路径，使得|n1-n2|+|n2-n3|+|n3-n4|+…+|ni-1 -ni|最小
输入第一行为列数，接下来的三行是具体的正整数
输入
1 | 5 |
2 | 5 9 5 4 4 |
3 | 4 7 4 10 3 |
4 | 2 10 9 2 3 |
输出
1 | 5 |
2 | 路径为5->7->5->4->4 |
分析
看到这道题目的时候，有想过用动态规划做，但是在笔试的时候紧张并且脑子不够用，没把状态分析出来，结束后去看了一下leetcode64，然后慢慢把这题分析出来。
首先定义一个3*n的二维dp数组，对于最后一列，初始化为0
从后往前分析，对于倒数第二列的第一个数字4，它的满足条件的最小值计算为 min{(4-4)+0,(4-3)+0,(4-3)+0}，同理依次计算第二个数字10和第三个数2，最终倒数第二列为 0,6,1。
对于倒数第三列的第一个数字5，满足条件的最小值计算为 min{(5-4)+,(5-10)+6,(5-2)+1},同理依次计算第二个数字和第三个数字，最终倒数第三列为 1，0，5
分析可知，dp{i}{j} = min{abs(input(i)(j) - input(0)(j+1)) + dp(0)(j+1),abs(input(i)(j) - input(1)(j+1)) + dp(1)(j+1),abs(input(i)(j) - input(2)(j+1)) + dp(2)(j+1)}
代码
代码就很简单了
1 | def solution(input_list): |
2 | len_ = len(input_list[0]) |
3 | dp_arr = [[0] * len_ for i in range(3)] |
4 | for j in range(len_ - 2, -1, -1): |
5 | for i in range(3): |
6 | dp_arr[i][j] = min(abs(input_list[i][j] - input_list[0][j + 1]) + dp_arr[0][j + 1], |
7 | abs(input_list[i][j] - input_list[1][j + 1]) + dp_arr[1][j + 1], |
8 | abs(input_list[i][j] - input_list[2][j + 1]) + dp_arr[2][j + 1]) |
9 | return dp_arr[:, 1] |
总结
这道题目一开始看，知道用dp，但是不知道怎么分析，做完之后回过头细细想慢慢能做出来，但是在笔试的时候，一开始想不出来就会乱，所以还是要多多训练啊，希望下次遇到这样的题目能迅速做出来吧。