当前位置: 首页 > news >正文

旅游网站开发的背景和意义php 新闻类网站怎么做

旅游网站开发的背景和意义,php 新闻类网站怎么做,网络营销专业的就业方向,wordpress仿哔哩哔哩题目链接:leetcode不同路径 目录 题目解析: 算法原理 1.状态表示 2.状态转移方程 3.初始化 4.填表顺序 5.返回值 编写代码 题目解析: 题目让我们求总共有多少条不同的路径可到达右下角; 由题可得: 机器人位于…

题目链接:leetcode不同路径


目录

题目解析:

算法原理

1.状态表示

2.状态转移方程

3.初始化

4.填表顺序

5.返回值

编写代码


题目解析:

题目让我们求总共有多少条不同的路径可到达右下角;

由题可得:

机器人位于一个 m x n 网格;

机器人每次只能向下或者向右移动一步;

我们拿示例2来分析:

则根据题目要求我们只能向下或者向右移动一步,不能向上或向左回退;

所以这里我们一共有三种走法:


算法原理:

1.状态表示

根据题目要求,先创建一个 m x n 大小的dp表

首先先思考dp表里面的值所表示的含义(是什么?)

dp[i][j]表示到达i*j时一共有多少种方式;

这种状态表示怎么来的?

1.经验+题目要求

经验:以i*j位置为结尾,

题目让我们求到达右下角有多少种方式,那么这里我们可以dp[i][j]来表示。

所以这里我们用i*j表示右下角位置;

2.状态转移方程

dp[i][j]等于什么?

用之前或者之后的状态,推导出dp[i][j]的值;

根据最近的最近的一步,来划分问题

当机器人到达dp[i-1][j]时,我们知道它到达[i-1][j]有dp[i-1][j]方式,

此时只需要从[i-1][j]往下走一步就可以到达目标位置,即:

……-->[i-1][j]-->(往下走一步)[i][j];

……-->[i-1][j]-->(往下走一步)[i][j];

……-->[i-1][j]-->(往下走一步)[i][j];

……

所以往下走一步就可以到达目标位置的方式就有dp[i-1][j]种;

那么同理,

当机器人到达dp[i][j-1]时,我们知道它到达[i][j-1]有dp[i][j-1]方式,

此时只需要在到达[i][j-1]方式的后面往右边走一步就可以到达目标位置,即:

……-->[i][j-1]-->(往右边走一步)[i][j];

……-->[i][j-1]-->(往右边走一步)[i][j];

……-->[i][j-1]-->(往右边走一步)[i][j];

……

所以往右边走一步就可以到达目标位置的方式就有dp[i-1][j]种;

综上所述,我们只要将到达[i][j-1]与[i-1][j]的总方法相加即可得到,到达[i][j]位置的总方法,

即:

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

3.初始化

(保证填表的时候不越界)

由我们的状态转移方程得:

在0行0列的时候越界,所以我们这里可以在m*n的外围多加1行1列,如图:

还有一个问题是:

我们要拿新增用来初始化的行和列要初始化为几呢?

假设:如果所需要到达的位置就在机器人所在的位置,此时有一种方式

根据状态转移方程,在[0][1]与[1][0]位置要有一个位置需要初始化为1,其他位置初始化为0

我们这里选择[0][1]初始化为1

4.填表顺序

(为了填写当前状态的时候,所需要的状态已经计算过了)

这里所需要的状态是:到达该位置的上面和左边位置的方式

所以填表顺序:

从上到下填写每一行

从左到右填写每一列

5.返回值

(根据题目要求和状态表示)

综上分析:

返回值为:dp[m][n];


编写代码:

class Solution {
public:int uniquePaths(int m, int n) {//1.创建dp表//2.初始化//3.填表//4.返回结果vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));dp[0][1]=1;for(int i=1;i<m+1;i++)for(int j=1;j<n+1;j++)dp[i][j]=dp[i][j-1]+dp[i-1][j];return dp[m][n];}
};

http://www.yayakq.cn/news/440690/

相关文章:

  • 漯河 网站建设邯郸网站建设效果
  • 青岛市城乡建设局网站网站设计论文的题目
  • 宁夏建设厅网站网站建设专业网站设计公司物格网
  • logo设计制作网站做特卖的网站
  • 国外手机网站源码西宁啥时候恢复正常
  • 专业建站公司建站系统网站建设技术包括哪些方面
  • 快设计网站官网wordpress dns预加载
  • 湖南省建设厅网站首页建设网站怎么克隆
  • 广东省建设厅人才网站wordpress版权文字
  • 绍兴做网站的公司企业管理app排行榜
  • 大型门户网站 代码wordpress 视频存储
  • 网站建设及报价格方案网页制作框架
  • 二级网站怎么建设营销系统官网
  • 网站热力图怎么做线上ui设计培训哪个好
  • 珠宝类网站建设可执行报告阿里云企业网站建设教程
  • 黔东网站建设36kr是用wordpress吗
  • 怎么用sharepoint做网站seo排名优化app
  • 二手网站开发论坛网站制作费用
  • 跨境电商网站系统开发在线设计平台崭露头角
  • 网站建设不挣钱wordpress大家都在搜
  • 做网站如何找项目wordpress无法安装导入器
  • 怎样批量做地级市网站网站免费网站免费优化优化
  • 网站维护的具体问题中铁建设企业门户
  • 社区论坛自助建站网大学生作业做网站
  • 怎么给公司做个网站合肥网站优化费用
  • 2015微信网站鄂州网站开发
  • 网站建设公司的做网站开发的公司销售
  • 增城建设局网站导航wordpress主题
  • 怎么把网站放到空间吗针织衫技术支持东莞网站建设
  • 网站策划预算怎么做网站开发er图