二维数组的DP问题

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

解决思路:动态规划

1、抽象状态,这个问题的状态很简单,就是走到第i行第j列的格子的时候,收集到的最大苹果数

F[i][j],其中0<=i<=N,0<=j<=M

2、问题转换方程,动态规划的思想就是要求原问题的解就要去子问题的解,这道题的子问题就是,找出能够到达当前格子的所有前一个格子的收集最大苹果数,然后加上当前格子的苹果数即可

F[I][j] = A[i][j]+max{if i>0:F[i-1][j] ; if j>0 :F[i][j-1]} //注意这里要考虑,如果第一行和第一列的特殊情况
  • 源码
import java.util.Scanner;
public class MaxApple {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int M = scanner.nextInt();
        int[][] A = new int[N][M];
        int[][] F = new int[N][M];
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                A[i][j] = scanner.nextInt();
            }
        }
        F[0][0]=A[0][0];  //初始化第一个格子

        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                int tempMax = Integer.MIN_VALUE;
                if(i==0&&j>0&&F[i][j-1]+A[i][j]>tempMax)  //第一行的情况
                    tempMax = F[i][j-1]+A[i][j];
                if(j==0&&i>0&&F[i-1][j]+A[i][j]>tempMax)  //第一列的情况
                    tempMax = F[i-1][j]+A[i][j];
                if(i>0&&j>0&&Math.max(F[i][j-1]+A[i][j],F[i-1][j]+A[i][j])>tempMax)
                    tempMax = Math.max(F[i][j-1]+A[i][j],F[i-1][j]+A[i][j]);
                if(i>0||j>0)
                F[i][j] = tempMax;
            }
        }
        System.out.println(F[N-1][M-1]);
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据魔术师

运筹学教学 | 十分钟快速掌握最大流算法(附C++代码及算例)

—“运筹教科书到底能给你啥?” —“算法和实现离教科书有多远?” —“问题解决能力到底从哪来?” 今天刚起床就接到了BOSS的 提·问·三·连 小编表示 收到直...

4935
来自专栏CSDN技术头条

Google核心技术之——PageRank算法scala实现

PageRank算法简述 常言道,看一个人怎样,看他有什么朋友就知道了。也就是说,一个人有着越多牛X朋友的人,他是牛X的概率就越大。将这个知识迁移到网页上就是“...

2556
来自专栏生信小驿站

主成分分析 factoextra

1023
来自专栏诸葛青云的专栏

迪杰斯特拉(dijkstra)c语言实现方法

迪杰斯特拉(dijkstra)是用来实现查找一个点到其它点最短路径的一种方法。通过查找从起点到最短距离的点,然后将该点放入到集合中,代表以及找到起点到这一点的最...

822
来自专栏编程札记

协同过滤Item-based算法实现电影推荐系统

1.3K3
来自专栏数据小魔方

动态地理信息可视化——leaflet在线地图简介

最近稍微涉猎了一下leaflet这个包,突然感到发现了动态可视化的新大门,这个包所提供的地图类型、动态效果、图层展示方式都大大扩展了ggplot作图系统的在数据...

4254
来自专栏携程技术中心

干货 | ElasticSearch相关性打分机制

作者简介 孙咸伟,后端开发一枚,在携程技术中心市场营销研发部负责“携程运动”项目的开发和维护。 携程运动是携程旗下新业务,主要给用户提供羽毛球、游泳等运动项目的...

1.4K8
来自专栏斑斓

Spark 1.4为DataFrame新增的统计与数学函数

Spark一直都在快速地更新中,性能越来越快,功能越来越强大。我们既可以参与其中,也可以乐享其成。 目前,Spark 1.4版本在社区已经进入投票阶段,在Gi...

3587
来自专栏大数据

有向无环图检测

01 — Spark背景介绍 Apache Spark 是专为大规模数据处理而设计的快速通用的计算引擎。Spark 是一种与 Hadoop 相似的开源集群计算环...

4107
来自专栏算法channel

Spark|有向无环图(DAG)检测

01 — Spark背景介绍 Apache Spark 是专为大规模数据处理而设计的快速通用的计算引擎。Spark 是一种与 Hadoop 相似的开源集群计算环...

5008

扫码关注云+社区