与记忆化

Question

动态规划由于我是新来的动态规划。有人可以帮助我实现算法的记忆技术以解决以下问题。

有N行和M列的2D矩阵。行从上到下从0到N-1，从左到右从0到M-1。你站在（0,0）。

从，A [i] [j]就可以移动到第[i + 1] [j]的如果A [1 + 1] [j]的> A [i] [j]。或者，如果A [i] [j + 1]> A [i] [j]，则可以将A [i] [j]移动到A [i] [j + 1]。

从（0,0）移动，那是什么，你可以旅行的最长路径？

static int a[][],n,m; 
static int find(int x,int y) 
{ 
    if((x==n-1 && y==m-1)) 
    { 
     return 1; 
    } 
    else if(x<n-1 && y<m-1 && a[x+1][y]>a[x][y] && a[x][y+1]>a[x][y]) 
    { 
     return Math.max(find(x+1,y),find(x,y+1))+1; 
    } 
    else if(x<n-1 && a[x+1][y]>a[x][y]) 
    { 
     return find(x+1,y)+1; 
    } 
    else if(y<m-1 && a[x][y+1]>a[x][y]) 
    { 
     return find(x,y+1)+1; 
    } 
    return 1; 
} 

其中.. x和y是初始位置（即（0,0））， n和m是行和列resply， 一个是实际的矩阵。

Answer 1

您想使用记忆化存储的find()的结果，以便您可以重新使用它们，如果你已经计算出他们已经：

1. 由m阵列（称之为memo说吧）的find()功能外声明另一个n
2. 之前从find()返回，存储计算结果memo[x][y]
3. 在find（）方法的开始，检查是否memo[x][y]已经填写（为非零）并返回它，如果它有