目录
  1. 1. 问题描述
  2. 2. 思路
  3. 3. 实现
    1. 3.1. 方法一
    2. 3.2. 方法二
算法-动态规划-最多苹果数

问题描述

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

思路

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

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

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

1
S[i][j]=A[i][j] + max(S[i-1][j],S[i][j-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)。需要单独处理。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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]的信息。这样代码就大大简化了,如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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]);
}
文章作者: 李浩
文章链接: https://leehoward.cn/2019/10/17/算法-动态规划-最多苹果数/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 leehoward
打赏
  • 微信
  • 支付宝

评论