Patent Document ID: 20130159372
Application ID: 13690333
Patent Flag: 0

Claim One:
1. A computer-implemented method for solving a dynamic programming problem, the method comprising: representing the dynamic programming problem as a matrix F of cells, each cell representing an intermediate score to be calculated, the matrix having a form: 
 F ( i,j )= G ( F ( i− 1, j− 1), F ( i, j− 1), F ( i− 1, j ), c ( i,j )), wherein i is a row index of the matrix F, wherein j is a column index of the matrix F, i and j respectively being larger than or equal to 0, wherein G is an optimization function and c is a cost function; providing a mapping, the mapping assigning cells of the matrix to elements of a result container data structure; providing the result container data structure for storing cells of the matrix F to elements of the result container data structure in accordance with the mapping; calculating intermediate scores of all cells F(i,j) of the matrix, whereby intermediate scores of some of the cells of the matrix are stored to a respectively assigned element of the result container data structure in accordance with the mapping; during the calculation of the intermediate scores, dynamically updating the assignment of cells and elements in the mapping such that: that first ones of the cells of the matrix are assigned to elements of the result container data structure respectively not having stored any intermediate score or having stored an intermediate score of second ones of the cells of the matrix, the first cells being calculated at a later moment in time than the second cells; that any intermediate scores of the second cells being overwritten by the intermediate scores of the first cells will not be required as input by any other ones of the matrix cells not having been calculated yet; and wherein the number of elements of the data structure is smaller than the number of cells of the matrix; and assembling a final result of the dynamic programming problem from the intermediate scores stored in the result container data structure.