上海金融网站建设公司,给网站做认证,东莞网站关键字,属于seo网站优化文章目录 题目思路代码 动态规划简介**一、什么是动态规划****二、动态规划的应用场景****三、动态规划的基本步骤****四、动态规划的优缺点** 题目
题目链接#xff1a;https://www.nowcoder.com/practice/9b969a3ec20149e3b870b256ad40844e?tpld230tpld39751ru/… 文章目录 题目思路代码 动态规划简介**一、什么是动态规划****二、动态规划的应用场景****三、动态规划的基本步骤****四、动态规划的优缺点** 题目
题目链接https://www.nowcoder.com/practice/9b969a3ec20149e3b870b256ad40844e?tpld230tpld39751ru/exam/oj 思路
有几个细节要明确
const[i]是在离开时花费的体力所以在离开时才会加根据例子我们能知道数组给了i个数我们下标到达i才算到顶如图如果我们必须到达cost[i1]才算登顶
动态规划
状态表示 dp[i]到达i位置所用最小花费状态转移方程 因为一次只能向上一个台阶或者两个台阶所以只有i-1,i-2两种可能。 dp[i]min(dp[i-1]cost[i-1],dp[i-2]cost[i-2]);代码
#include iostream
using namespace std;#define N 100010int main() {int cost[N]{0};int dp[N]{0};int n;cin n;for(int i0;in;i)cin cost[i];for(int i2;in;i)dp[i]min(dp[i-1]cost[i-1],dp[i-2]cost[i-2]);cout dp[n] endl;return 0;
}动态规划简介
一、什么是动态规划
动态规划Dynamic Programming是一种在解决多阶段决策问题时常用的算法思想。它通过将复杂问题分解成一系列相互关联的子问题并按照一定的顺序求解这些子问题从而避免了重复计算提高了算法的效率。上面的题的思想就是动态规划。
动态规划的核心思想是“最优子结构”和“重叠子问题”。最优子结构意味着一个问题的最优解包含了其子问题的最优解。重叠子问题则是指在求解过程中相同的子问题会被多次计算。
二、动态规划的应用场景
动态规划在许多领域都有广泛的应用例如
求解最短路问题如在图中找到从一个节点到另一个节点的最短路径。 例如在一个城市交通网络中寻找从起点到终点的最短行驶路线。 资源分配问题如何合理分配有限的资源以达到最优效果。 比如在项目管理中合理分配人力和时间资源以使项目能够在最短时间内完成。 背包问题给定一组物品和一个背包容量选择哪些物品放入背包能使价值最大化。
三、动态规划的基本步骤
定义状态表示明确问题中的状态变量这些变量通常用来描述子问题的解。建立状态转移方程找出不同状态之间的关系确定如何从一个状态转移到另一个状态。初始化边界条件确定初始状态的值。按照合适的顺序计算状态值通常是从边界条件开始逐步计算其他状态的值。
四、动态规划的优缺点
优点
能够有效地降低算法的时间复杂度避免重复计算。对于具有最优子结构和重叠子问题的问题能够得到最优解。
缺点
空间复杂度可能较高需要存储状态值。状态定义和转移方程的推导可能比较困难需要对问题有深入的理解。
总之动态规划是一种强大的算法思想掌握它对于解决许多复杂的优化问题具有重要意义。但在实际应用中需要根据具体问题的特点来选择是否使用动态规划以及如何设计有效的算法。
