# 谷歌店面

Given a m-by-n grid: every element is non-negative integer.

Constrains:
(1) a path only contain non-zero cells
(2) a path can extend to 4 directions: up, down, left, right
(3) no same cell in a path
Assumption
(4) cells with non-0 number will not form a cycle

Find the maximum path sum.

Example 1:

Input:
5 4 1 0
1 0 1 2
3 0 0 4
0 1 2 0

Output: 21
Explanation: 3 -> 1 -> 5 -> 4 -> 1 -> 1 -> 2 -> 4

Example 2:

Input:
5 4 1 3
1 0 1 0
3 0 0 4
0 1 2 0

Output: 17
Explanation: 3 -> 1 -> 5 -> 4 -> 1 -> 3

1一个二维矩阵，按up-right顺序输出
ex:mat= [[1,2,3]
[4,5,6]
[7,8,9]], output: 1,4,2,7,5,3,8,6,9
followup: what if the vectors in mat is not uniforly sized, namely not a rectangular matrix?
My answer: find the longest vector in mat, and we can do it as a rectangular matrix
2. there is a list of words l=[there, is,a bunch, bunches, of, words], target string thereisabunchofwords, return if the
target string can be formed by using words in list l?
followup: what if words in l can only be used once?