快手算法笔试A卷题python实现

快手笔试题一共四道算法题，时间为两个小时，第三道和第四道需要长期积累，笔者两个小时只撸出来两道题，尤其是第四道题需要高等数学、微积分等等知识：

快手算法笔试A卷第一道编程题：

给定正整数N，将其分成K份，保证每一份都是正整数，求这些正整数乘积的最大值。
比如：给定（），可以得到结果：

python实现（耗时一个小时10分钟）：

import math
def KN_1(K, N, result):
    if K==1 or N==1:
        return result*N
    min_result = math.ceil(N/K)
    N = N - min_result
    K = K - 1
    result = result * min_result
    return KN_1(K, N, result)

if __name__ == '__main__':
    result = KN_1(3, 7, 1)
    print(result)

快手算法笔试A卷第二道编程题：

给定一个N*M的矩阵，从（0,0）出发到（N-1，N-1），每一次只能向下或者向右，求最优（最短）路径。
比如：给定（），可以得到结果：

python实现（耗时30分钟）：

    def minPathSum(grid):
        m, n = len(grid), len(grid[0])
        dp = []
        for i in range(m):
            dp.append([0 for _ in range(n)])

        for i in range(m):
            for j in range(n):
                if i == 0:
                    dp[i][j] = dp[i][j-1] + grid[i][j]
                else:
                    if j == 0:
                        dp[i][j] = dp[i-1][j] + grid[i][j]
                    else:
                        dp[i][j] = min(dp[i-1][j], dp[i][j-1])+grid[i][j]
        return dp[m-1][n-1]

if __name__ == '__main__':
    result = minPathSum([[1,2,3],[4,5,6],[7,8,9]])
    print(result)