## 矩阵求解问题(数据结构)

4546 发布于 2016/06/19 18:19

[1,2,3
4,5,6,
7,8,9
]

### 以下是问题补充：

@4546：其实是n*n的矩阵,对矩阵进行遍历,每次只能向右或者向下走,走到[n-1][n-1]为一次遍历结果,求在所有遍历过程中的最大和,用递归思想要如何做,我找不到判断递归结束的点 (2016/06/19 23:46)

1

4

4

0

1x+2y=3z

4x+5y=6z

7x+8y=9z

1  2  3

4  5  6

7  8  9

0

```WITH temp AS (
SELECT ROWNUM rn, MOD(ROWNUM-1,3)+1 x, CEIL(ROWNUM/3) y
FROM dual CONNECT BY ROWNUM <= 9
)
,board(x,y,amount,path,lv) AS (
SELECT x, y, rn, to_char(rn), 1 FROM temp WHERE x = 1 AND y = 1
UNION ALL
SELECT t.x, t.y, b.amount+t.rn, b.path||' + '||t.rn, b.lv+1
FROM board b, temp t
WHERE b.lv < 9
AND INSTR(b.path,t.rn) = 0
AND (b.y = t.y AND t.x-b.x = 1
OR b.x = t.x AND t.y-b.y = 1)
)
SELECT * FROM board WHERE x = 3 AND y = 3;```

21 = 1 + 2 + 3 + 6 + 9
23 = 1 + 2 + 5 + 6 + 9
25 = 1 + 2 + 5 + 8 + 9
25 = 1 + 4 + 5 + 6 + 9
27 = 1 + 4 + 5 + 8 + 9

29 = 1 + 4 + 7 + 8 + 9

0
4

#### 引用来自“jolphin”的评论

```WITH temp AS (
SELECT ROWNUM rn, MOD(ROWNUM-1,3)+1 x, CEIL(ROWNUM/3) y
FROM dual CONNECT BY ROWNUM <= 9
)
,board(x,y,amount,path,lv) AS (
SELECT x, y, rn, to_char(rn), 1 FROM temp WHERE x = 1 AND y = 1
UNION ALL
SELECT t.x, t.y, b.amount+t.rn, b.path||' + '||t.rn, b.lv+1
FROM board b, temp t
WHERE b.lv < 9
AND INSTR(b.path,t.rn) = 0
AND (b.y = t.y AND t.x-b.x = 1
OR b.x = t.x AND t.y-b.y = 1)
)
SELECT * FROM board WHERE x = 3 AND y = 3;```

21 = 1 + 2 + 3 + 6 + 9
23 = 1 + 2 + 5 + 6 + 9
25 = 1 + 2 + 5 + 8 + 9
25 = 1 + 4 + 5 + 6 + 9
27 = 1 + 4 + 5 + 8 + 9

29 = 1 + 4 + 7 + 8 + 9