这是一个创建于 3481 天前的主题，其中的信息可能已经有所发展或是发生改变。
最近折腾了几天的搜索、回溯、动规……结果到现在连数塔都写不对😂，看了半天看不出毛病，只能又跑来找大大们了……
题目：
第一行输入数塔层数 N
以下 N 行为从最顶层到最底层每一层的数字
输入样例：
5
7
3 8
8 1 0
2 7 7 4
4 5 2 6 5
输出样例：
30
错误代码😂：
题目：
第一行输入数塔层数 N
以下 N 行为从最顶层到最底层每一层的数字
输入样例：
5
7
3 8
8 1 0
2 7 7 4
4 5 2 6 5
输出样例：
30
错误代码😂：
 |
1
xjx0524 2014-10-28 22:20:02 +08:00  1
score=score-a[i][j];这句放到条件语句外面来
|
 |
2
etolew 2014-10-28 22:28:40 +08:00 1
同小白，路过。。。
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)同理。 |
 |
3
spencerqiu OP @xjx0524
虽然好像还是不对，按照样例输入，输出的是 24 。不过能不能粗略讲讲这么做的原因？ |
|
4
spencerqiu OP |
|
5
spencerqiu OP @etolew
奇怪……执行之后还是不对耶…… |
|
6
spencerqiu OP 按照楼上两位大大的修改方法，虽然都不对，但是不对的是一样的，都是 24 ……
好神奇😂 |
|
7
etolew 2014-10-28 22:57:12 +08:00
|
|
8
xjx0524 2014-10-28 23:06:29 +08:00
@etolew 你这么改是不对的啊，楼主的做法是当前这层递归score就加上遍历到的结点值，你减去下一层的值显然不对。
@spencerqiu 我跟你说的那个改法原因是if(i==n)之后要返回上一层递归了但是没有减去当前的a[i][j] |
|
9
xjx0524 2014-10-28 23:08:55 +08:00
@etolew 不好意思看错了，你把score=score-a[i][j];这句话也删了，结果是对的。但是逻辑上最好不要这样做，当层做的改变应该当层就恢复。
|
 |
10
ffffwh 2014-10-29 03:45:32 +08:00
这个用DFS是依然会有重复计算的吧
|
 |
11
oaix 2014-10-29 11:33:13 +08:00
方法错了，应该使用 DP。
|
Select Language