Java-动态规划-最多苹果数量的方法

java

平面上有N*M个格子,每个格子中放着一定数量的苹果。你从左上角的格子开始,每一步只能向下走或是向右走,每次走到一个格子上就把格子里的苹果收集起来,这样下去,你最多能收集到多少个苹果。


思路:

解这个问题与解其它的DP问题几乎没有什么两样。第一步找到问题的“状态”,第二步找到“状态转移方程”,然后基本上问题就解决了。

首先,我们要找到这个问题中的“状态”是什么?我们必须注意到的一点是,到达一个格子的方式最多只有两种:从左边来的(除了第一列)和从上边来的(除了第一行)。因此为了求出到达当前格子后最多能收集到多少个苹果,我们就要先去考察那些能到达当前这个格子的格子,到达它们最多能收集到多少个苹果。 (是不是有点绕,但这句话的本质其实是DP的关键:欲求问题的解,先要去求子问题的解)

经过上面的分析,很容易可以得出问题的状态和状态转移方程。状态S[i][j]表示我们走到(i, j)这个格子时,最多能收集到多少个苹果。那么,状态转移方程如下:

S[i][j]=A[i][j] + max(S[i-1][j],S[i][j-1])


方法1:常规方法,dp[i][j]数组保存当前路径下最多苹果个数,它是由MAX{dp[i-1][j] ,dp[i][j-1]} + a[i][j]。循环遍历,最后即可获取结果。但是我们需要额外考虑第0列、第0行这两个特殊情况,因为他们只有0种(i=0且j=0)或1种可能(i=0或j=0)。需要单独处理。代码如下:

public static void dp2(int a[][],int M,int N){

int dp[][] = new int[M][N];

int i=0,j=0;

for ( i=0;i<M;i++){

for ( j=0;j<N;j++){

if (i==0&&j==0){//考虑顶点

dp[i][j] = a[i][j];

continue;

}

if (i==0){//考虑第一行

dp[i][j] = dp[i][j-1] + a[i][j];

continue;

}

if (j==0){//考虑第一列

dp[i][j] = dp[i-1][j] + a[i][j];

continue;

}

if (dp[i-1][j]>dp[i][j-1]){//状态转移

dp[i][j] = dp[i-1][j] + a[i][j];

}else {

dp[i][j] = dp[i][j-1] + a[i][j];

}

}

}

System.out.println(dp[M-1][N-1]);

}



方法二,增加两行两列,存储状态,如dp[i+1][j+1] 存储的是a[i][j]的状态,这样的话就不用考虑顶点和第一行第一列的特殊情况,因为dp[1][1]存储的是a[0][0]的路径状态信息,dp[1][3]存储的是a[0][2]的信息。这样代码就大大简化了,如下:

 public static void dp(int a[][],int M,int N){

int dp[][] = new int[M+2][N+2];

int i=0,j=0;

for ( i=0;i<M;i++){

for ( j=0;j<N;j++){

if (dp[i+1][j]>dp[i][j+1]){

dp[i+1][j+1] = dp[i+1][j] + a[i][j];

}else {

dp[i+1][j+1] = dp[i][j+1] + a[i][j];

}

}

}

System.out.println(dp[M][N]);

}




以上是 Java-动态规划-最多苹果数量的方法 的全部内容, 来源链接: utcz.com/z/394350.html

回到顶部