LeetCode热题100——动态规划

news/2024/7/17 3:44:30

动态规划

  • 1. 爬楼梯
  • 2. 杨辉三角
  • 3. 打家劫舍

1. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

// 题解:每次都有两种选择,1或者2
int climbStairs(int n) {if (n <= 0) return 0;vector<int> dp(n+1, 0);dp[0] = 1;dp[1] = 1;for (int i = 2; i <= n; ++i) {dp[i] = dp[i-1] + dp[i-2];}return dp[n];
}

2. 杨辉三角

给定一个非负整数 numRows,生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中,每个数是它左上方和右上方的数的和。
在这里插入图片描述

// 题解:从第三层开始,累计和
vector<vector<int>> generate(int numRows) {vector<vector<int>> result(numRows);for (int i = 0; i < numRows; ++i) {result[i].resize(i+1);reult[i][0] = result[i][i] = 1;for (int j = 1; j < i; ++j) {result[i][j] = result[i-1][j] + result[i-1][j-1];}}return result;
}

3. 打家劫舍

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

// 题解:和上次结果比较,取最大值
int rob(vector<int>& nums) {int length = nums.size();if (length == 0) return 0;vector<int> dp(length+1, 0);dp[1] = nums[0];for (int i = 2; i <= length; ++i) {dp[i] = max(dp[i-1], dp[i-2] + nums[i-1]);}return dp[length];
}

https://www.xjx100.cn/news/3092682.html

相关文章

模电 01

一.半导体基本知识 1.优点&#xff1a;体积小、重量轻、使用寿命长、输入功率小、功率转换效率高。 2.性能介于导体与绝缘体 3.常用半导体材料&#xff1a;硅&#xff08;SI&#xff09; 镉&#xff08;Ge&#xff09;,化合物半导体&#xff1a;砷化镓&#xff08;GaAs&…

linux上安装qt creator

linux上安装Qt Creator 1 Qt Creator 的下载 下载地址为&#xff1a;http://download.qt.io/archive/qt/ 根据自己的需求选择Qt Creator版本&#xff0c;这里我下载的是5.12.9&#xff0c;如下图所示&#xff1a; 在ubuntu上可以使用wget命令下载安装包&#xff1a; wget h…

微信小程序记住密码,让登录解放双手

密码是用户最重要的数据&#xff0c;也是系统最需要保护的数据&#xff0c;我们在登录的时候需要用账号密码请求登录接口&#xff0c;如果用户勾选记住密码&#xff0c;那么下一次登录时&#xff0c;我们需要将账号密码回填到输入框&#xff0c;用户可以直接登录系统。我们分别…

前端CSS实现响应式TimeLine效果(附源码)

文章目录 纯CSS搭建&#xff0c;先上效果图&#xff08;附有源码&#xff09;视图层 index.htmlindex.css 公用样式文件Main.css 主要的样式文件 纯CSS搭建&#xff0c;先上效果图&#xff08;附有源码&#xff09; 本效果为纯CSS搭建&#xff0c;适配移动端和PC端&#xff01…

2023年【T电梯修理】考试题及T电梯修理考试报名

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 T电梯修理考试题是安全生产模拟考试一点通总题库中生成的一套T电梯修理考试报名&#xff0c;安全生产模拟考试一点通上T电梯修理作业手机同步练习。2023年【T电梯修理】考试题及T电梯修理考试报名 1、【多选题】GB/T1…

Continuity” of stochastic integral wrt Brownian motion

See https://imathworks.com/math/math-continuity-of-stochastic-integral-wrt-brownian-motion/

gitlab安装配置及应用

安装 ##安装依赖 yum install -y curl policycoreutils-python openssh-server perl#上传包 rz gitlab-jh-16.5.2-jh.0.el7.x86_64.rpm 安装 yum install gitlab-jh-16.0.3-jh.0.el7.x86_64.rpm 初始化并启动 # 以下两种方法都可以配置访问地址&#xff0c;第一种需要在yum安…

小程序制作(超详解!!!)第十六节 小程序的基本架构

1.题目描述 创建一个包含:首页、教学、科研、资讯和关于我们5个标签的小程序&#xff0c;每个标签都有对应的页面、图标和标签文字&#xff0c;点击某个标签将切换到对应的页面&#xff0c;同时该标签的图标和文字颜色都会发生变化页面的标题也发生相应的变化&#xff0c;而其…