Google – Cost to Transfer Files

Google – Cost to Transfer Files
给两个整数m和n，表示一个matrix的行和列，matrix里每个cell是一台电脑，从一台电脑传文件到另一台电脑的cost就是他们俩之间的manhattan distance. 题目的要求是把整个matrix里每一台电脑都从其他电脑接收文件，求出所有的cost之和。
比如m = 3, n = 2, matrix就是
1 1
1 1
1 1
每台电脑接收文件的cost为
9 9
7 7
9 9
总和为50.
[Solution]
典型DP问题，不过转移方程不太常见。
lookup[i][j] represents the total cost for current computer to receive all files from others.
lookup[i][j] = lookup[i][j – 1] + j * m – (n – j) * m
or
lookup[i][j] = lookup[i – 1][j] + i * n – (m – i) * n
Either one is ok, but do not add them together!
Space Complexity might be optimized to O(n) cause we only reply on result from either left or above cell.

给两个整数m和n，表示一个matrix的行和列，matrix里每个cell是一台电脑，从一台电脑传文件到另一台电脑的cost就是他们俩之间的manhattan distance. 题目的要求是把整个matrix里每一台电脑都从其他电脑接收文件，求出所有的cost之和。

比如m = 3, n = 2, matrix就是
1 1
1 1
1 1

每台电脑接收文件的cost为
9 9
7 7
9 9

总和为50.

[Solution]
典型DP问题，不过转移方程不太常见。
lookup[i][j] represents the total cost for current computer to receive all files from others.

lookup[i][j] = lookup[i][j – 1] + j * m – (n – j) * m
or
lookup[i][j] = lookup[i – 1][j] + i * n – (m – i) * n
Either one is ok, but do not add them together!

Space Complexity might be optimized to O(n) cause we only reply on result from either left or above cell.

Read full article from Google – Cost to Transfer Files