网站建设策划书怎么写,从网站开发到游戏编程,设计公司网页制作,可拖拽编程网站开发一、最小路径和
1、题目解析 就是一个人从左上往做下走#xff0c;每次只能往右或者往下#xff0c;求他到终点时#xff0c;路径上数字和最小#xff0c;返回最小值 2、算法原理
a状态表示方程
小技巧#xff1a;经验题目要求
用一个二维数组表示#xff0c;创建一个…一、最小路径和
1、题目解析 就是一个人从左上往做下走每次只能往右或者往下求他到终点时路径上数字和最小返回最小值 2、算法原理
a状态表示方程
小技巧经验题目要求
用一个二维数组表示创建一个二维数组 dp[i][j] 表示当前从起点到当前节点的最小值 b状态转移方程
一个小技巧找到最近的一步划分问题
能到达dp[i][j]的只有一条路径上或者左边选择一个两者较小的值。因为dp[i-1][j]或者dp[i][j-1]也是表示他那个节点对路径最小值——问题进入闭环
dp[i][j]min(dp[i-1][j],dp[i][j-1])grid[i][j] c初始化
以下面这张图为例为了避免越界访问我们本来应该在1,1的位置开始遍历的。给第一行和第一列进行初始化。 为了简化这个过程我们给它多创建一行多创建一列再给里面赋上合适的值这样避免了越界访问也避免了初始化繁琐的操作我们可以直接进行填表。 既然要选取较小值那我们就直接弄上最大值INT_MAX然后在0,1和1,0的位置附上0就行了这样dp[1][1]就能保证刚好就是grid[0][0]这样从1开始的每一列都是获取上面的路径和每一行都是获取左边的路径和这样就是合理的赋值。 这其实就是运用了虚拟节点来进行初始化简化初始化的行为。
这种方法需要注意两点
进行合理赋值保证后面填表的值是正确的注意取值的下标映射
因为我们的dp表是多了一行多了一列我们需要i-1,j-1才能取到正确的值
d填表顺序
从左到右从上到下
e返回值
dp[m][n] 3、代码
class Solution {
public:int minPathSum(vectorvectorint grid) {//建dp表//初始化//填表//返回值int mgrid.size();int ngrid[0].size();vectorvectorint dp(m1,vectorint(n1,INT_MAX));dp[0][1]0;dp[1][0]0;for(int i1;im;i){for(int j1;jn;j){dp[i][j]min(dp[i-1][j],dp[i][j-1])grid[i-1][j-1];}}return dp[m][n];}
};
二、地下城游戏
1、题目解析 这道题相较于第一题多了负数但是还是有可以一样的处理——进行相加并且还多了一个限制条件骑士的值不能为零。也是只能向下和向右走。不过这道题需要返回骑士需要救到公主所需最低的健康值。 2、算法原理
a状态表示方程
经验题目要求
有两种解题方式
1、以某个位置为结尾。。。。。
假设dp[i][j]表示从期待您出发到达ij位置数所需的最低健康点数
这个思路其实是错误的因为你不仅需要进入这个房间还要静茹下一个房间这就导致了你不能简单的通过这个房间的前一步进行判断还需要考虑后续房间的影响。————有后效性
2、以某个位置为起点。。。。。
dp[i][j]表示从这李出发到达终点所需最低初始健康。 b状态转移方程
根据最近的一步划分问题
假设进入d[i][j]这个房间所需最小生命值为x 其实想要右边房间的话就需要xd[i][j]dp[i][j1]
xdp[i][j1]-d[i][j] 还有一种特殊情况需要我们考虑如果房间里面是一个较大血包的话dp[i][j1]-d[i][j]是有可能小于0的————这表示你就算是负多少多少都能够走到终点但这是不合理的负数骑士都死掉了。
所以 c初始化
虚拟节点处理边界问题的好方法 这道题需要考虑边界问题是最后一行和最后一列。
需要注意的两点
1、设置合适的值保证填表时值的正确性 走出迷宫最少得剩下一滴血
2、注意下标映射
因为是添加在最后一行和最后一列不需要考虑下标问题 d填表顺序
从下往上从右往左
e返回值
dp[0][0]
3、代码
class Solution {
public:int calculateMinimumHP(vectorvectorint dungeon) {//建表//初始化//填表//返回值int mdungeon.size(),ndungeon[0].size();vectorvectorint dp(m1,vectorint (n1,INT_MAX));dp[m][n-1]1;dp[m-1][n]1;for(int im-1;i0;i--){for(int jn-1;j0;j--){int tmin(dp[i1][j],dp[i][j1])-dungeon[i][j];dp[i][j]max(1,t);}}return dp[0][0];}
};
