前置:基础语法
最低所需知识点:动态规划
首先观察题目要求可以得知Hello Kitty(什么唐人名字)摘花生的限制为只能向东或向南走不能向北或向西
所以稍加思索 转换一下限制条件
每个点都只会走最多一次 且不能走回头路
观察数据范围 数据较大 所以不适用于dfs 考虑动规
先读入一个二维矩阵记为z
同样设置一个二维的动态规划数组记为dp
设置状态表达为到第i j时最多可以摘dp[i][j]个花生
由前面的限制得状态状态转移方程:
dp[i][j]=max(dp[i-1][j],dp[i][j-1])+z[i][j];
注意:
为了防止数组越界 需要在状态转移方程上动一些小手脚(整体思路不变)
注意dp数组初始化
具体代码在题解区查收
------------------------------------------------------------题解结束------------------------------------------------------------