小白笨死了， DFS 写的都不对……好伤心，求大大带

This topic created in 4219 days ago, the information mentioned may be changed or developed.

最近折腾了几天的搜索、回溯、动规……结果到现在连数塔都写不对😂，看了半天看不出毛病，只能又跑来找大大们了……

题目：
第一行输入数塔层数 N
以下 N 行为从最顶层到最底层每一层的数字

输入样例：
5
7
3 8
8 1 0
2 7 7 4
4 5 2 6 5

输出样例：
30

错误代码😂：

回溯

输入

最底层

11 replies • 2014-10-29 11:33:13 +08:00

xjx0524

Oct 28, 2014

score=score-a[i][j];这句放到条件语句外面来

etolew

Oct 28, 2014

同小白，路过。。。
22-24行改成
dfs(i+1,j);
score=score-a[i+1][j];
dfs(i+1,j+1);
score=score-a[i+1][j+1];

dfs调用之后是要恢复到上一步，
dfs(i+1,j)里是把score加了a[i+1][j]，
所以应该减去它。
dfs(i+1,j+1)同理。

spencerqiu

Oct 28, 2014 via iPad

@xjx0524
虽然好像还是不对，按照样例输入，输出的是 24 。不过能不能粗略讲讲这么做的原因？

spencerqiu

Oct 28, 2014 via iPad

@etolew
哈，谢谢，看懂了。

虽然写了这么多次回溯，一直对这种回溯条件感觉怪怪的😂

spencerqiu

Oct 28, 2014 via iPad

@etolew
奇怪……执行之后还是不对耶……

spencerqiu

Oct 28, 2014 via iPad

按照楼上两位大大的修改方法，虽然都不对，但是不对的是一样的，都是 24 ……

好神奇😂

etolew

Oct 28, 2014

@spencerqiu
我可以吐槽一下吗。。。
粘你代码的时候我直接顺手改了就忘了

第17行，多了一个分号，所以结果是7+8+4+5=24

xjx0524

Oct 28, 2014

@etolew 你这么改是不对的啊，楼主的做法是当前这层递归score就加上遍历到的结点值，你减去下一层的值显然不对。

@spencerqiu 我跟你说的那个改法原因是if(i==n)之后要返回上一层递归了但是没有减去当前的a[i][j]

xjx0524

Oct 28, 2014

@etolew 不好意思看错了，你把score=score-a[i][j];这句话也删了，结果是对的。但是逻辑上最好不要这样做，当层做的改变应该当层就恢复。

ffffwh

Oct 29, 2014

这个用DFS是依然会有重复计算的吧

oaix

Oct 29, 2014

方法错了，应该使用 DP。