top_k_path

Description
A robot is located at the top-left corner of a m×n
 grid. The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid. There is a non-negative integer in each small grid which means the score that the robot get when it passes this grid. Now you need to calculate the top k
 total scores when the robot reach the destination.

Note: The top k total scores may contain same total score got from different paths.

Input
The first line of input are m and n,which denote the size of the grid. The second line of input is the k
. The next m lines are the score matrix. (1≤m,n,k≤100
,and 0≤score≤100
)

Output
There is only one line in the Output,which is a descending sequence consist of the top k total scores.

Sample1
Input

3 3
2
3 2 5
3 2 2
4 2 1
Output

13 13
Sample2
Input

4 3
3
7 1 5
4 6 2
4 2 1
5 7 3
Output

30 29 27

My code:
import numpy as np
class Solution:
    def find_kpath(self, m,n,k,matrix):
        x=0
        y=0
        self.record=np.zeros([m,n])-1
        self.operation = np.zeros([m, n]) - 1
        output=[]
        count=1
        result=self.find_opt(m,n,0,0,matrix)
        #Get all the path
        path_list=[]
        tmp_list=[]
        path_list.append(tmp_list)
        self.get_path_list(0,0,m,n,self.operation,path_list,0)
        for i in range(len(path_list)):
            output.append(int(result))
        if len(path_list)>=k:
            return output[0:k]
        operation=[]
        for i in range(len(path_list)):
            operation.append(np.array(self.operation))
        record_list=[]
        for i in range(len(path_list)):
            record_list.append(np.array(self.record))
        self.look_more(matrix,path_list,output,operation,record_list,k-len(path_list),m,n)
        if len(output)<k:
            print('not so many paths to find out')
            return output
        final_out=output[0:k]
        return final_out
        #For other situations, we need to modify the code
    def find_opt(self,m,n,x,y,matrix):
        if x==m or y==n:
            return 0

        if self.record[x,y]!=-1:
            return self.record[x,y]
        result1=self.find_opt(m,n,x+1,y,matrix)
        result2=self.find_opt(m,n,x,y+1,matrix)
        if result1>result2:
            self.record[x,y]=matrix[x,y]+result1
            self.operation[x,y]=0#Denotes going down
        else:
            self.record[x, y] = matrix[x, y] + result2
            if result1==result2 and (x!=m-1 and y!=n-1):
                self.operation[x,y]=2#Denotes going right operation
            else:
                self.operation[x, y] = 1  # Denotes going right operation
        return self.record[x,y]
    def get_path_list(self,x,y,m,n,operation,path_list,path_id):
        if x==m or y==n:
            return

        path_list[path_id].append((x*n+y))
        operationtmp=operation[x,y]
        if operationtmp==1:
            y+=1
            self.get_path_list(x,y,m,n,operation,path_list,path_id)
        elif operationtmp==0:
            x+=1
            self.get_path_list(x, y, m, n, operation, path_list, path_id)
        elif operationtmp==2:
            #print('x %d y %d'%(x,y))
            tmp_list=[]
            for item in path_list[path_id]:
                tmp_list.append(item)
            path_list.append(tmp_list)
            self.get_path_list(x+1, y, m, n, operation, path_list, path_id)
            self.get_path_list(x, y+1, m, n, operation, path_list, len(path_list)-1)

    def look_more(self,matrix, path_list, output, operation, record_list, rotate_times,m,n):
        if rotate_times<=0:
            return
        close=100000000
        add_path=[]
        for i in range(len(path_list)):
            tmp_path=path_list[i]
            tmp_operation=operation[i]
            tmp_record=record_list[i]
            tmp_output=output[i]
            for j in range(len(tmp_path)):
                tmp_xoy=tmp_path[j]
                x=int(np.floor(tmp_xoy/n))
                y=int(tmp_xoy%n)
                #print('x %d y %d and operation %d'%(x,y,tmp_operation[x,y]))
                now_operation=tmp_operation[x,y]
                now_record=tmp_record[x,y]
                change_record=tmp_record[x,y]
                if now_operation==0:
                    #previously choose x,now we choose y
                    if y+1<n:
                        change_record=tmp_record[x,y+1]+matrix[x,y]

                elif now_operation==1:
                    if x+1<m:
                        change_record = tmp_record[x+1, y] + matrix[x, y]
                #print('previous record %d, now record %d'%(tmp_record[x,y],change_record))
                if change_record<now_record:
                    #check if it's in pathlist
                    tmp_change_path=[]
                    tmp_change_operation=np.array(tmp_operation)
                    if now_operation==0:
                        tmp_change_operation[x,y]=1
                    elif now_operation==1:
                        tmp_change_operation[x, y]=0
                    tmp_list=[]
                    tmp_change_path.append(tmp_list)
                    self.get_path_list(0, 0, m, n, tmp_change_operation, tmp_change_path, 0)
                    #print(tmp_list)
                    total_change=now_record-change_record
                    total_now=tmp_output-total_change
                    tmp_path_can_use=[]
                    for item in tmp_change_path:
                        if item not in path_list:#Check if this updated path has existed
                            tmp_path_can_use.append(item)
                    if len(tmp_path_can_use)>0:
                        close_tmp=output[-1]-total_now
                        if close>close_tmp:
                            #Save for adding use
                            close=close_tmp
                            add_operation=tmp_change_operation
                            add_path=tmp_path_can_use
                            tmp_use_record=np.array(tmp_record)
                            tmp_use_record[x,y]=change_record
                            add_record=tmp_use_record
                            add_total=total_now
        #Add new record in record list
        if len(add_path)>0:

            for i in range(len(add_path)):
                path_list.append(add_path[i])
                output.append(int(add_total))
                operation.append(add_operation)
                record_list.append(add_record)
            rotate_times=rotate_times-len(add_path)
            self.look_more(matrix, path_list, output, operation, record_list, rotate_times, m, n)








solu=Solution()
m=3
n=3
matrix=np.array([[3, 2, 5],[3, 2, 2],[4, 2, 1]])
k=8
result=solu.find_kpath(m,n,k,matrix)
print(result)