算法打卡day33|动态规划篇01|动态规划理论基础| Leetcode 509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯

admin2024-04-03  0

动态规划理论

定义

动态规划的主要理论基础包括最优性原理、无后效性和有重叠子问题三个性质:

在实际应用中,动态规划已被广泛应用于各类问题,如路径优化、资源分配、生产调度、库存管理和投资组合等优化问题。例如,在路径优化问题中,可以将路径划分为多个阶段,每个阶段的状态表示为路径的一部分,决策表示为选择哪条路径,然后通过动态规划算法求出最优路径。

动态规划的解题步骤

这里推荐卡哥总结的动规五步曲:

状态转移公式(递推公式)是很重要,但动规不仅仅只有递推公式。

对于动态规划问题,将拆解为如下五步曲,将五步都搞清楚,才能是把动态规划真的掌握了

  1. 确定dp数组(dp table)以及下标的含义

  2. 确定递推公式

  3. dp数组如何初始化

  4. 确定遍历顺序

  5. 举例推导dp数组

这里之所以要先确定递推公式,然后在考虑初始化,是因为一些情况是递推公式决定了dp数组要如何初始化其实 确定递推公式 仅仅是解题里的一步而已!搞不清楚dp数组应该如何初始化,或者正确的遍历顺序,以至于记形忘神。

算法题

Leetcode 509. 斐波那契数

题目链接:509. 斐波那契数

 大佬视频讲解:斐波那契数视频讲解

 个人思路

熟悉的课后题,递推公式题目就直接给了,只用初始化数值,然后遍历即可;

解法
动态规划

虽然是道简答题,也要好好分析直至慢慢掌握动规。

动规五部曲:

用一个一维dp数组来保存递归的结果

1.确定dp数组以及下标的含义

dp[i]的定义为:第i个数的斐波那契数值是dp[i]

2.确定递推公式

题目已经把递推公式直接出:状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];

3.dp数组如何初始化

题目中把如何初始化也直接给出了:

dp[0] = 0;
dp[1] = 1;

4.确定遍历顺序

5.举例推导dp数组

代码写出来可以打印一下,如果一样就ok,不一样则debug一下

class Solution {
    public int fib(int n) {
        if (n <= 1) return n;             
        int[] dp = new int[n + 1];
        dp[0] = 0;//初始化
        dp[1] = 1;

        for (int index = 2; index <= n; index++){//遍历
            dp[index] = dp[index - 1] + dp[index - 2];//递推公式
        }
        return dp[n];
    }
}

 Leetcode  70. 爬楼梯

题目链接:70. 爬楼梯

大佬视频讲解:爬楼梯视频讲解

个人思路

和上一题有些相像,递推公式也是一样的,所以也是很快就能解决;o.O先找找动规做题自信

解法
动态规划

动规的题目如果一眼看不出规律,就多举几个例子就行;

动规五部曲:

定义一个一维数组来记录不同楼层的状态

1.确定dp数组以及下标的含义

dp[i]: 爬到第i层楼梯,有dp[i]种方法

2.确定递推公式

3.dp数组如何初始化

4.确定遍历顺序

从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出,遍历顺序一定是从前向后遍历

5.举例推导dp数组

举例当n为5的时候,dp table(dp数组)应该是这样的

算法打卡day33|动态规划篇01|动态规划理论基础| Leetcode 509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯,第1张

与斐波那契数列唯一的区别是dp[0]在本题没有意义!

public int climbStairs(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 1;//初始化
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {//遍历
        dp[i] = dp[i - 1] + dp[i - 2];//地推公式
    }
    return dp[n];
}

 Leetcode  746. 使用最小花费爬楼梯

题目链接:746. 使用最小花费爬楼梯

大佬视频讲解:使用最小花费爬楼梯视频讲解

个人思路
解法
动态规划

1.确定dp数组以及下标的含义

dp[i]的定义:到达第i台阶所花费的最少体力为dp[i]

2.确定递推公式

3.dp数组如何初始化

4.确定遍历顺序

因为dp[i]由dp[i-1]dp[i-2]推出,所以是从前到后遍历cost数组

5.举例推导dp数组

拿示例2:cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ,来模拟一下dp数组的状态变化,如下:

算法打卡day33|动态规划篇01|动态规划理论基础| Leetcode 509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯,第2张

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int len = cost.length;
        int[] dp = new int[len + 1];//dp数组

        // 从下标为 0 或下标为 1 的台阶开始,因此支付费用为0
        dp[0] = 0;
        dp[1] = 0;

        // 计算到达每一层台阶的最小费用
        for (int i = 2; i <= len; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }

        return dp[len];
    }
}

 以上是个人的思考反思与总结,若只想根据系列题刷,参考卡哥的网址代码随想录算法官网

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!