|
l*n
发帖数: 529 | 2 你是对的，楼上楼也提到pathmin跟accu的冲突，我原来想的错误比较是用pathmin[i,
j-1]跟pathmin[i-1, j]，即便修正为比较"考虑了accu的"从上面和左边进入的两个假
想pathmin，也无法解决局部和全局的问题。每次比较进入[i,j]的两个假想的pathmin
，也可能会错过全局的最优，因为可能存在的情况是某个在中途不是给出最优pathmin
的路径反而能给出全局最优。
一个反例就是
6 -12 4 13
-1 -9 5 -3
-5 -11 -16 -17
-8 -13 5 -8
每次都要求进入当前位置的pathmin为最优导致选择-1 -9 5 ...的路径，其pathmin是-
1 -10 -10，但是在5的位置accu是-5，而brutal force给出的路径是-12 4 5...，在5
位置的accu是-3，而其pathmin是-12 -12 -12...。
这种局部最优策略跟全局最优的冲突，极端起来怕是每一处都需要走两条线。看来这个
harry potter的题目只能brutal force了。 |
|
l*n
发帖数: 529 | 3 确实，greedy思路走岔了，不过在考虑greedy accu怎么着路径的时候发现必须要有两
个matrix来dp，一个是accu， 一个是pathmin。
accu(i, j)=pathmin(i-1, j)>pathmin(i, j-1)?
accu(i-1, j)+input(i, j):
accu(i, j-1)+input(i, j);
pathmin(i， j)=pathmin(i-1, j)>pathmin(i, j-1)?
min(pathmin(i-1, j), accu(i, j)):
min(pathmin(i, j-1), accu(i, j));
better |
|
l*n
发帖数: 529 | 4 这样来分析吧。假设我们用brutal force方法解了问题，那么我们能够知道走到最右下
角时符合题设的路径中的最低strength。能对最右下角做，也就能对任何坐标点做。假
设现在知道了pathmin(i, j-1)和pathmin(i-1,j)，也就是当坐标的左边和上边，那为
了走到当前坐标会如何走？进当前坐标格只有两个入口，或者左或者上，显然选的是
pathmin高的那个。一旦入口选定了，当前坐标的累计值accu就决定了，然后当前坐标
格的pathmin也就决定了。
这里pathmin不是记录的某个path的最低streng，而是所有能走到当前坐标格的路径中
最优路径的最低accu值。
is |
|
l*n
发帖数: 529 | 5 accu(accumulate)如其名字，是记录最优的path走到当前位置的累计值。
pathmin是走到当前位置的最优路径的最小accu值，假设路径上input矩阵的值是2>>5>>
-3>>-2>>4>>2的话，accu就是2>>7>>4>>2>>6>>8，而一路上pathmin的值是2>>2>>2>>2>
>2>>2。
这里ifelse的逻辑就是，进入某一个位置只能是从左边或者上边的cell，左边cell的
pathmin值比上边的pathmin要高的话，初始需要的strength就更低，所以从左边进入当
前cell。 |
|
l*********b
发帖数: 1541 | 6 虽然左边的pathmin比较高，但是上边的accu可能比较大。比如：左边的pathmin比较大
，但是accu是10，上边的accu是20， 当前cell的stength是－15，这时候要选上边的吧？
>>
2> |
|
w*******s
发帖数: 138 | 7 Harry Potter是二分搜索答案，对于每个答案，用DP判断是否可行。
一开始随便找一条路设初始值。
,
pathmin
pathmin |
|
l*n
发帖数: 529 | 8 我在调试，一会儿post。
你这个1>>1>>1>>1>>-5>>0的情况，对应的accu是1>>2>>3>>4>>-1>>-1，
而pathmin是1>>1>>1>>1>>-1>>-1，应该是对的。
>( |
|
l*********b
发帖数: 1541 | 9 if (lefmin > upmin) {
accu[i][j] = accu[i][j - 1] + mat[i][j];
} else if (lefmin < upmin) {
accu[i][j] = accu[i - 1][j] + mat[i][j];
}
上面两个if／else不是很明白， 感觉不能推出上面两个吧。。 请问你这个pathmin和
accu分别代表啥？ |
|
