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

wordpress用别人主题seo排名培训学校

wordpress用别人主题,seo排名培训学校,河南做网站哪个平台好,域名注册好如何做网站目录 题目 例子 示例 1: 示例 2: 前言 思路 思想 代码 调用的函数 主函数 所有代码 力扣提交的代码 运行结果 小结 题目 给定一个三角形 triangle ,找出自顶向下的最小路径和。 每一步只能移动到下一行中相邻的结点上。相邻的结…

目录

题目

例子

示例 1:

示例 2:

前言

思路

思想

代码

调用的函数

主函数

所有代码

力扣提交的代码

运行结果

小结


题目

给定一个三角形 triangle ,找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标 i 或 i + 1 。

例子

示例 1:

输入:triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出:11
解释:如下面简图所示:23 46 5 7
4 1 8 3
自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。

示例 2:

输入:triangle = [[-10]]
输出:-10

前言

本题是动态规划的一道经典题目,最早出现在1994年的ioi比赛中

经过了20多年的时间,如今已经变成了动态规划的入门必做题

思路

我们可以以下面的图来举例子

设置数据为一个二维数组(或者是一个容器)

放入[2],[3,4],[6,5,7],[4,1,8,3]四组数据

我们可以很简单的看出来——最短路径是2,3,5,1

如果把走到响应的点所得到的和(也就是所求值)定义为一个二维数组的话

我们可以得到一个4*4的二维数组(当然其中有一些是用不到了)

那可以把题目转化为求最底下行数组的值,并且比较大小得出最小值

我可以知晓除去第一列的值,其中随机一列的值只取决上一列与其相邻的值,因此我们可以设置递归函数,第a[i][j]的值只取决与原来数组本身的值加上a[i-1][j]与a[i-1][j-1]的最小值。

从底下迭代是一种方法

但是他会有一个问题,他会重复大量计算相同的数字

比如上面的例子:

第三行第一列以及第二列都需要知道第二行第一列的数字,所以第二行第一列的值会计算两遍

思想

所以结果就是我从上向下迭代

下一行的数字只会取上一行的值,然而上一行的值都是计算好的

不需要重新计算也不存在重复以及浪费时间

有些相当于广度优先了

那么思想有了

就是代码实现了

代码

调用的函数

int minimumTotal(vector<vector<int>>& triangle) {int length_1 = triangle.size();int length_2 = triangle[length_1-1].size();vector <vector<int>> n(length_1, vector<int>(length_1, 0));for (int i = 0; i <= length_1 - 1; i++){if (i == 0){n[0][0] = triangle[0][0];continue;}for (int j = 0; j <= i; j++){if (j == 0){n[i][0] = n[i - 1][0] + triangle[i][0];continue;}if (j == i){n[i][i] = n[i - 1][i - 1] + triangle[i][i];continue;}n[i][j] = min(n[i - 1][j - 1] + triangle[i][j], n[i - 1][j] + triangle[i][j]);}}int min = n[length_1 - 1][0];for (int i = 0; i <= length_2 - 1; i++)if (n[length_1 - 1][i] < min)min = n[length_1 - 1][i];return min;
}

思想就是上面讲到的思想

需要注意的是第一行以及第一列与最后一列要单独考虑

主函数

int main()
{vector <vector<int>>sum_1 = { {2} ,{3,4},{6,5,7},{4,1,8,3} };int min = minimumTotal(sum_1);cout << min << endl;return 0;
}

所有代码

#include <iostream>
#include <vector>
#include <string>
using namespace std;
int minimumTotal(vector<vector<int>>& triangle) {int length_1 = triangle.size();int length_2 = triangle[length_1-1].size();vector <vector<int>> n(length_1, vector<int>(length_1, 0));for (int i = 0; i <= length_1 - 1; i++){if (i == 0){n[0][0] = triangle[0][0];continue;}for (int j = 0; j <= i; j++){if (j == 0){n[i][0] = n[i - 1][0] + triangle[i][0];continue;}if (j == i){n[i][i] = n[i - 1][i - 1] + triangle[i][i];continue;}n[i][j] = min(n[i - 1][j - 1] + triangle[i][j], n[i - 1][j] + triangle[i][j]);}}int min = n[length_1 - 1][0];for (int i = 0; i <= length_2 - 1; i++)if (n[length_1 - 1][i] < min)min = n[length_1 - 1][i];return min;
}
int main()
{vector <vector<int>>sum_1 = { {2} ,{3,4},{6,5,7},{4,1,8,3} };int min = minimumTotal(sum_1);cout << min << endl;return 0;
}

力扣提交的代码

class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {int length_1 = triangle.size();int length_2 = triangle[length_1-1].size();vector <vector<int>> n(length_1, vector<int>(length_1, 0));for (int i = 0; i <= length_1 - 1; i++){if (i == 0){n[0][0] = triangle[0][0];continue;}for (int j = 0; j <= i; j++){if (j == 0){n[i][0] = n[i - 1][0] + triangle[i][0];continue;}if (j == i){n[i][i] = n[i - 1][i - 1] + triangle[i][i];continue;}n[i][j] = min(n[i - 1][j - 1] + triangle[i][j], n[i - 1][j] + triangle[i][j]);}}int min = n[length_1 - 1][0];for (int i = 0; i <= length_2 - 1; i++)if (n[length_1 - 1][i] < min)min = n[length_1 - 1][i];return min;
}
};

运行结果

小结

本期博客介绍了现在的动态规划的经典题目,并且提供了3种方法,

(入了个门,相当于?)

http://www.tj-hxxt.cn/news/35676.html

相关文章:

  • 有域名如何做免费网站广东东莞疫情最新消息今天又封了
  • 白云区同和网站建设cpa推广接单平台
  • 免费做国际网站互联网电商平台有哪些
  • 成人高考成绩查询温州企业网站排名优化
  • 网站建设申请理由万网域名查询
  • wordpress 分类添加图片杭州seo技术培训
  • 网站变慢的原因云优客seo排名公司
  • 青岛网络公司有哪些推荐seo关键词优化
  • 什么网站可以做邮件列表如何在百度上添加店铺的位置
  • 昭阳区建设局网站网页设计制作网站模板
  • php动态网站开发教程发文章用哪个平台比较好
  • 海珠营销网站建设报价合肥seo培训
  • 企业网站手机版模板游戏推广怎么做引流
  • 怎么做游戏网站seo怎么收费的
  • 如何做网站窗口中国旺旺(00151) 股吧
  • 广州哪里有网站建设凡科建站登录
  • 石家庄企业名录大全太原关键词优化报价
  • 做针织衫的网站百度搜索结果优化
  • 蓬莱做网站价格网站排名推广工具
  • 建设局官网查询seo代做
  • 给个网站急急急202友情链接平台赚钱吗
  • 做网站做地区好还是全国的好带佣金的旅游推广平台有哪些
  • 国内好的网站建设陕西seo公司
  • 苹果手机推广网站制作友情链接导航
  • 中国机械加工网加热炉节能信阳seo推广
  • 深圳网站建设怎样做cms快速建站
  • 哪些调查网站可以做问卷赚钱百度口碑网
  • 国内服务器做网站要备案站长工具永久
  • dota2max网站怎么做壁纸百度手机
  • 水头做网站的公司百度竞价推广属于什么广告