Day39- 动态规划part07

时间:2024-02-11 23:44:16 标签:  动态  

一、爬楼梯

题目一:57. 爬楼梯

57. 爬楼梯(第八期模拟笔试)

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 

每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢? 

注意:给定 n 是一个正整数。

输入描述

输入共一行,包含两个正整数,分别表示n, m

输出描述

输出一个整数,表示爬到楼顶的方法数。

到达第n个台阶的方法数量是到达前面某些台阶的方法数量的总和,具体来说,就是到达第n-1, n-2, ..., n-m个台阶的方法数量的总和,因为每次可以爬1到m个台阶。

定义一个数组dp,其中dp[i]表示到达第i个台阶的方法数。

初始化dp[0] = 1,因为到达起点(不爬任何台阶)只有一种方法。

然后,对于每一个台阶i(从1到n),计算到达这个台阶的方法数,即dp[i] = dp[i-1] + dp[i-2] + ... + dp[i-m],其中i-m > 0

对于那些i < m的台阶,只能从比i小的台阶爬上来,所以在这种情况下,dp[i]应该是dp[i-1] + dp[i-2] + ... + dp[0]

#include <iostream>
#include <vector>
using namespace std;int climbStairs(int n, int m) {vector<long long> dp(n + 1, 0); dp[0] = 1; for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m && i - j >= 0; ++j) {dp[i] += dp[i - j];}}return dp[n];
}int main() {int n, m;cin >> n >> m;cout << climbStairs(n, m) << endl;return 0;
}

二、零钱兑换

题目一:322. 零钱兑换

322. 零钱兑换

给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。

你可以认为每种硬币的数量是无限的。

dp[i]代表组成金额i所需的最少硬币数。

初始化dp[0] = 0,因为金额为0时不需要任何硬币。

对于所有其他的i,可以初始化为一个很大的数,比如amount + 1,这个值代表无效解,因为组成金额i最多使用的硬币数不会超过amount

对于每个金额i1amount,遍历所有的硬币面额,更新dp[i]为:

dp[i]=\min(dp[i],dp[i-\text{coin}]+1)

/** @lc app=leetcode.cn id=322 lang=cpp** [322] 零钱兑换*/// @lc code=start
class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount + 1, amount + 1);dp[0] = 0;for (int i = 1; i <= amount; i++) {for (int coin : coins) {if (i - coin >= 0) {dp[i] = min(dp[i], dp[i - coin] + 1);}}}return dp[amount] > amount ? -1 : dp[amount];}
};
// @lc code=end

三、完全平方数

题目一:279. 完全平方数

279. 完全平方数

给你一个整数 n ,返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,149 和 16 都是完全平方数,而 3 和 11 不是。

初始时,dp[0] = 0,因为组成数0不需要任何完全平方数。

动态规划的状态转移方程为:

dp[i]=\min_{1\leq j^2\leq i}\{dp[i-j^2]+1\}

/** @lc app=leetcode.cn id=279 lang=cpp** [279] 完全平方数*/// @lc code=start
class Solution {
public:int numSquares(int n) {vector<int> dp(n + 1, INT_MAX); dp[0] = 0; for (int i = 1; i <= n; ++i) {for (int j = 1; j*j <= i; ++j) {dp[i] = min(dp[i], dp[i - j*j] + 1);}}return dp[n];}
};
// @lc code=end
来源:分享自作者个人站点/博客

智能推荐

一、爬楼梯 题目一&#xff1a;57. 爬楼梯 57. 爬楼梯&#xff08;第八期模拟笔试&#xff09; 题目描述 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。  每次你可以爬至多m (1 <&#61; m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢&#xff1f;  注意&#xff1a;给定 n 是一个正整数。 输入描述 输入共一行&#xff0c;包含两个正整数&#xff0c;分别表示n, m 输出描述 输出一个整数&#xff0c;表示爬到楼顶的方法数。

标签:动态  

一、概述1.设计思想动态规划法将待求解问题分解成若干个相互重叠的子问题,每个子问题对应决策过程的一个阶段,通过组合子问题而解决整个问题的解。2.基本要素(1)最优子结构最优性原理体现为问题的最优子结构特性。当一个问题的最优解中包含了子问题的最优解

标签:动态  

动态规划(Dongtai Planning&nbsp;Dynamic Programming,简称DP)&nbsp; &nbsp; &nbsp;多阶段决策过程的最优化问题在现实生活中,有一类活动的过程,由于它的特殊性,可将过程分成若干个互相联系的阶段,在它的每一阶段都需要作出决策,从而使整个过程达到最好的活动效果。当然,各个阶段决策的选取不是任意确定的,它依赖于当前面临的状态,又影响以后的发展,当各个阶段决策确定后,就组成一个决策序列,因而也就确定了整个过程的一条活动路线,这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程,这种问题就称为多

标签:动态  

作者推荐 视频算法专题 简介 动态规划&#xff08;Dynamic Programming&#xff0c;DP&#xff09;是运筹学的一个分支&#xff0c;是求解决策过程最优化的过程。每次决策依赖于当前状态&#xff0c

标签:动态  

动态规划part07 70.爬楼梯&#xff08;进阶&#xff09; 322. 零钱兑换 279. 完全平方数 70.爬楼梯&#xff08;进阶&#xff09;&#xff08;题目链接点我&#xff09; #include&

标签:进阶  

作者推荐 【动态规划】【广度优先搜索】【状态压缩】847 访问所有节点的最短路径 本文涉及知识点 动态规划汇总 LeetCode879. 盈利计划 集团里有 n 名员工&#xff0c;他们可

标签:计划  

文章目录 动态规划理论基础动规五部曲&#xff1a;出现结果不正确&#xff1a; 62.不同路径63. 不

标签:路径  

什么是动态规划?今天简单说一下动态规划的定义以及简单示例。动态规划,是一种将原问题分解成简单的子问题来解决复杂问题的思想。其中,动态规划还具有最优子结构性质和子问题重叠性质。最优子结构:动态规划将原问题分解成各种简单的子问题时,各个子问题的最优解综合起来就是原问题的最优解,即局部最优解能够决定全局最优解。子问题重叠:在计算一个子问题的最优解之后,记住这个子问题,接下来还可能遇到相同问题,为提高效率,可以直接拿来之前得到的结果,这是因为当使用递归自顶向下的时候,每次产生的子问题不总是新问题,而是之前被重复计算的问题。斐

标签:动态  

Hello Kitty想摘点花生送给她喜欢的米老鼠。她来到一片有网格状道路的矩形花生地(如下图),从西北角进去,东南角出来。地里每个道路的交叉点上都有种着一株花生苗,上面有若干颗花生,经过一株花生苗就能摘走该它上面所有的花生。Hello Kitty只能向东或向南走,不能向西或向北走。问Hello Kitty最多能够摘到多少颗花生。

标签:动态  摘花  

动态规划的引入动态规划(Dynamic Programming,DP)是运筹学的一个分支,是求解决策过程最优化的过程。20世纪50年代初,美国数学家贝尔曼(R.Bellman)等人在研究多阶段决策过程的优化问题时,提出了著名的最优化原理,从而创立了动态规划。动态规划的应用极其广泛,包括工程技术、经济、工业生产、军事以及自动化控制等领域,并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。​

标签:动态  

总结 动态规划的的四个解题步骤是&#xff1a; 定义子问题写出子问题的递推关系确定 DP 数组的计算顺序空间优化&#xff08;可选&#xff09; from functools import cache&#64;cache #缓存&#xff0c;避免重复运算def dfs(i)->int:if 终止: return 0 #具体返回什么值要看题目的含义cnt &#61; 0for 递归方向:cnt &#43;&#61; dfs(xxx) #如果是计数&#xff0c;一般是叠加&#xff

标签:例题  

一、动态规划定义通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。二、动态规划与贪心算法区别已知问题规模为n的前提A,求解一个未知解B。(我们用An表示“问题规模为n的已知条件”)此时,如果把问题规模降到0,即已知A0,可以得到A0->B.如果从A0添加一个元素,得到A1的变化过程。即A0->A1; 进而有A1->A2; A2->A3; …… ; Ai->Ai+1. 这就是严格的归纳推理,也就是我们经常使用的数学归纳法;对于Ai+1,只需要它的上一个状态Ai即可完成整个推理过程(而不需要更前序的状态)。我们将这一模型称为马尔科夫模型。对应的推理过程叫做“贪心法”

标签:算法  动态  

本题是一道背包上限可以变化的多重部分和问题,此处给出了粗略题解题目来源:(未知)题面题目描述llk经常和wy一起去yh小饭馆吃盖浇饭,一天他们吃完后llk把两个人的钱一起付了,但是wy不想欠llk的钱。现在wy手中有一些散钱,llk手中也有一些散钱,wy想知道能不能刚好使得两不相欠,但是wy很笨,你能帮助wy吗?输入多组测试数据,每组第一行输入3个非负整数,C,n,m。C代表wy欠llk的钱,n代表wy手中钱面值的种类,m代表llk手中钱面值的种类。

标签:欠债还钱  动态  

python 动态规划性质最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质(即满足最优化原理)。最优子结构性质为动态规划算法解决问题提供了重要线索。子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时,每次产生的子问题并不总是新问题,有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只计算一次,然后将其计算结果保存在一个表格中,当再次需要计算已经计算过的子问题时,只是在表格中简单地查看一下结果,从而获得较高的效率。无后效性:即某阶段状态一旦确定,就

标签:经典  动态  python  

题目 一个给定的正整数序列&#xff0c;在每个数之前都插入&#43;号或-号后计算它们的和。比如序列&#xff1a;1、2、4共有8种可能的序列&#xff1a; (&#43;1) &#43; (&#43;2) &#43; (&#43;4) &#61; 7 (&#43;1) &#43; (&#43;2) &#43; (-4) &#61; -1 (&#43;1) &#43; (-2) &#43; (&#43;4) &#61; 3 (&#43;1) &#43; (-2) &#43; (-4) &#61; -5 (-1) &#43; (&#43;2) &#43; (&#43;4) &#61;

标签:动态  

509、斐波那契数和爬楼梯一样,最基础的动态规划,没什么好说的。class Solution{public: int fib(int n) { if (n == 0) { return 0;

标签:题记  动态  LeetCode  

392.判断子序列&#xff1a; 初始思路&#xff1a;                  左为判断公共子序列&#xff0c;右为判断子序列&#xff0c;感觉代码完

标签:序列  

什么是动态规划动态规划(英语:Dynamic programming,简称 DP),是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。&nbsp;&nbsp;&nbsp;

标签:矩阵  动态  

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi&#xff0c;价值是 wi。 求解将哪些物品装入背包&#xff0c;可使这些物品的总体积不超过背包容量&#xff0c;且总价值最大。 输出最大价值。 输入格式 第一行两个整数&#xff0c;N&#xff0c;V&#xff0c;用空格隔开&#xff0c;分别表示物品数量和背包容积。 接下来有 N 行&#xff0c;每行两个整数 vi,wi&#xff0c;用空格隔开&#xff0c;分别表示第 i 件物品的体积和价值。 输出格式 输出一个整数&#xff0c;表示最大价值

标签:背包  

01背包问题 动态规划 01背包问题 动态规划写了点代码 C#实现程序运行结果代码和程序已经上传 01背包问题 动态规

标签:背包  

Peter推荐算法书&#xff1a;《算法导论》 图示&#xff1a; 目录 钢条切割

标签:算法  

&#x1f9d1;‍&#x1f4bb; 文章作者&#xff1a;Iareges &#x1f517; 博客主页&#xff1a;https://blog.csdn.net/raelum ⚠️ 转载请注明出处

标签:背包  

目录 一、基础理论 二、例题

标签:动态  

本题力扣上没有&#xff0c;是刷的卡码网第52题52. 携带研究材料感兴趣的小伙伴可以去刷一下&#xff0c;是ACM模式。 题目&#xff1a; 题目描述&#xff1a; 小明是一位科学家&#xff0

标签:背包  

猜你喜欢

动态规划算法&#xff08;DP&#xff09;&#xff1a;在马尔可夫决策过程&#xff08;MDP&#xff09;的完美环境模型下计算最优策略。但其在强化学习中实用性有限&#xff0c;其一是它是基于环境模型已知&#xff1b;其二是它的计算成本很大。但它在理论伤仍然很重要&

标签:动态  

目录1 多阶段决策和最优化原理1.1 用递推法求最短路1.2 资源分配问题1.3 前向优化和后向优化2 定期多阶段决策问题2.1 背包问题2.2 最长公共子序列问题2.3 旅行售货员问题3 不定期多阶段决策问题3.1 一般图上的最短路问题3.2 单汇点最短路问题4 连续变量的多阶段决策问题4.1 资源分配问题1 多阶段决策和最

标签:运筹学  动态  

动态规划求解子序列问题 1.子序列&#xff08;不连续&#xff09;1.1最长上升子序列1.2最长公共子序列1.3不相交的线 2.子序列

标签:之子  

Search当一个大问题是由多个子问题构成时,我们可以通过不断分解问题来最终构建我们想求的大问题。这个过程成为搜索(Search)。搜索空间(Search Space)可以用Tree的形式展现出来,便于理解。时间复杂度取决于这棵树的深度和每个node的children个数。Search 最重要的就是定义好状态,保证每个子问题都能用一个状态来描述Search没有重复子问题,但DP有。DP(Dynamic Programming)如果我们Search Space有重复子问题的话,可以记录下这些子问题的答案来保证不会重复计算多次。所以DP也被称为Search+Me

标签:题型  算法  动态  

样例输入4 3样例输出9提示样例输入2 复制13 13样例输出2 复制156这题用动态规划做。首先审题,发现如果要求H(n,m

标签:函数  动态  BUCTOJ  Harnack  

62. 不同路径。 一个机器人位于一个 m x n 网格的左上角 &#xff08;起始点在下图中标记为 “Start” &#xff09;。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角&#xff08;在下图中标记为 “Finis

标签:路径  

选择>行动>思考&#xff0c;好像是个死循环 -song。  动态规划&#xff08;Dynamic Programming&#xff0c;简称DP&#xff09;是一种解决问题的数学优化方法&#xff0c;通常用于解决具有重叠子问题和最优子结构性质的问题。它的基本思想是将问题拆分成小的子问题&#xff0c;先求解并保存子问题的解&#xff0c;然后通过这些子问题的解来求解原

标签:例子  

参考博客&#xff1a;https://leetcode.cn/problems/interleaving-string/solutions/48146/dong-tai-gui-hua-zhu-xing-jie-shi-python3-by-zhu-3

标签:字符串  

目录 第一章&#xff1a;动态规划算法理论基础

标签:算法  

动态规划框架动态规划:Dynamic Programming动态规划问题的一般形式就是求最值 -> 穷举动态规划的穷举特点在于这类问题存在重叠子问题,如果暴力穷举,效率极其低下。所以一般通过备忘录或者DP table用空间来优化穷举的过程,避免不必要的计算。动态规划三要素:重叠子问题、最优子结构、状态转移方程重叠子问题:最优子结构:

标签:框架  动态  LeetCode  

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi &#xff0c;价值是 wi 。 求解将哪些物品装入背包&#xff0c;可使这些物品的总体积不超

标签:背包  

灵感来源: https://zhuanlan.zhihu.com/p/91582909最近实在是被动态规划伤透了脑筋,今天看到这篇文章感觉醍醐灌顶一般的突然就茅塞顿开,记好这三步,动态规划就不难了,这里开篇文章记录一下,我是如何用这个方法来刷剑指offer的动态规划题的;当然每个题都有更好的解决方法,但是我们的思路是先用陈咬金的三板斧解决了问题再来进行优化,下面简述一下思路:第一步: 下定义定义要求解的问题为合适的结构,一般都是一维数组或二维数组;第二步骤:定初值

标签:动态  板斧  这三  难题  三步走  

作者推荐 【动态规划】【字符串】扰乱字符串 本文涉及的基础知识点 动态规划 LeetCode312 戳气球 有 n 个气

标签:气球  

作者推荐 【动态规划】【字符串】扰乱字符串 本文涉及的基础知识点 动态规划 LeetCode312 戳气球 有 n 个气球&#xff0c;编号为0 到 n - 1&#xff0c;每个气球上都

标签:气球  

作者推荐 【动态规划】【数学】【C&#43;&#43;算法】18赛车 涉及知识点 动态规划 LeetCode741 摘樱桃 给你一个 n x n 的网格 grid &#xff0c;代表一块樱

标签:樱桃  

目录 1143.最长公共子序列

标签:第二天  

Problem: 343. 整数拆分 文章目录 题目描述思路解题方法复杂度Code

标签:整数  

动态规划——区间DP 学习笔记不含四边形不等式优化。定义线性动态规划的局限性在于,它只能顺推或倒退,而不能有子区间依赖的问题。区间动态规划是线性动态规划的扩展,它将问题划分为若干个子区间,并通过定义状态和状态转移方程来求解每个子区间的最优解,最终得到整个区间的最优解。区间动态规划常用于解决一些涉及区间操作的问题,是一种高效的求解区间最优值的方法,可以有效地解决各种区间问题。性质子区间可拆分:即能将问题分解为能两两合并的形式;子区间独立性:即将区间

标签:区间  学习笔记  动态  dp  

题目连接:337. 打家劫舍 III - 力扣(LeetCode)&nbsp;&nbsp;题目分析:  二叉树的后续遍历,dp[root] 表示 root节点的最大收益&nbsp; &nbsp; &nbsp; &nbsp; dp[root] = max(dp[root.left] + dp[root.rig

标签:打家劫舍  动态  III  

问题描述输入格式输出格式样例代码

标签:路径  题目  动态  dp  

有 N 组物品和一个容量是 V 的背包。 每组物品有若干个&#xff0c;同一组内的物品最多只能选一个。 每件物品的体积是 vij &#xff0c;价值是 wij &#xff0c;其中 i 是组

标签:背包  

作者推荐 【动态规划】【字符串】【表达式】2019. 解出数学表达式的学生分数 本文涉及知识点 动态规划汇总 LeetCode1388 3n 块披萨 给你一个披萨&#xff0c;它由 3n

标签:披萨  

目录 [NOIP2001 提高组] 数的划分题目描述输入格式输出格式样例 #1

标签:动态  

目录 [NOIP2001 提高组] 数的划分题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1

标签:动态  

作者推荐 视频算法专题 涉及知识点 动态规划 字符串 LeetCode87扰乱字符串 使用下面描述的算法可以扰乱字符串

标签:字符串  

相关问题

相关文章

热门文章

推荐文章

相关标签