• LetCode刷题[简单题](5)按摩师,迭代出最优解(卡尔曼滤波也是类似迭代)


    所有的遍历寻求有条件约束的最大值都可以转换成,新的数带来的最大值的变化,问题往这个方向转化就可以,问题都是在最中进行选择的,因此关注的问题最大值得上限就好了,不必关注可能随机的下限。关注随机可能的下限会把问题想的更复杂了,往混沌方向走了,思维要清晰简单把握最新变化的可能性。

    1. class Solution {
    2. public:
    3. int massage(vector<int>& nums) {
    4. //最优计算方式,构建最优计算方法
    5. //分类讨论场景1 在顺序中选择插空排列组合
    6. int n = nums.size(); //一共有多少的数据总量
    7. if (n == 0) {
    8. return 0;
    9. }
    10. if (n == 1) {
    11. return nums[0];
    12. }
    13. int prev1 = nums[0]; //前一个数据
    14. int prev2 = std::max(nums[0], nums[1]); //第一个数据与第二个数据中取最大值
    15. //还是采用迭代的思路,迭代
    16. for (int i = 2; i < n; i++) { //从第二个数据开始计算
    17. int current = std::max(prev2, prev1 + nums[i]); //第二天与第一天
    18. prev1 = prev2;
    19. prev2 = current;
    20. }
    21. return prev2;
    22. //最终留下来的都是最大值迭代选法。采用的是迭代的选法
    23. //采用数学里归纳法迭代的思路来演化,使用递归应该也能解决
    24. }
    25. };

    迭代最优解思路。

    本题的思路,因为需要访问计算每一次的数据得到最大的那个值,为了n长的数组中,符合slect规律的话,可以先解决 n-1长度的情况下的选择最大值,因为选择是有限制的随机,并且最大的可能是不选,最小值是0,那么问题就会转化为,n长的数组规模下,n-1,给n数组带来变数的可能性,针对问题特性,新的数字给最大值带来了新的可能性那就是相隔一个的选择情况下加上新的n位置的数产生了最大值,或者当初n-1个数的值依然保持最大。这两种比较就可以得到n的时候的最大值。

    迭代在计算机中具有许多优势,这些优势使它成为解决问题的常用方法之一:

    1. 空间效率: 迭代通常使用的内存空间相对较小,因为它只需要在内存中保留有限数量的变量和数据结构。相比之下,递归可能需要维护递归调用的堆栈,占用更多内存。

    2. 时间效率: 迭代通常比递归更快,因为它避免了递归调用的开销。递归调用需要保存当前函数的状态、参数等信息,并在递归返回时恢复这些状态,而迭代仅使用循环来执行操作,减少了这些开销。

    3. 可读性: 迭代往往更容易理解和调试,因为它是一个线性的控制流结构。递归可能会变得更加复杂,因为它涉及到函数的嵌套调用,难以跟踪和理解。

    4. 栈保留: 迭代通常更容易控制和限制栈的深度。递归调用可能会导致栈溢出,特别是对于大规模的问题,而迭代可以更容易地避免这种情况。

    5. 优化: 编译器和解释器通常能够对迭代代码进行更好的优化,因为它们能够更容易地分析和理解迭代的行为,从而提高性能

  • 相关阅读:
    Docker部署Tomcat及Web应用
    学GoWorld,go 1.21
    网络安全宣传周|这些网络安全知识赶紧get起来~
    设计模式——12. 策略模式
    【力扣】35. 搜索插入位置
    常用的数据库连接池、配置参数及相应的调优方法
    软件项目管理 6.7.参数估算法
    Hopcroft–Karp algorithm
    Linux 动、静态库原理深剖
    PUK码怎么解锁
  • 原文地址:https://blog.csdn.net/u013590327/article/details/133887422