数据结构和算法

分类

读书笔记(1) 题解(70)

/ 注册

TA的专栏 76篇文章 67人订阅

数据结构和算法

73篇文章 54597人学习

常见数据结构介绍

3篇文章 606人学习

全部文章（共11篇）

【数据结构和算法】最小花费爬楼梯来自专栏

解法一如果到第i个台阶，我们可以从第i-1个台阶跳一步上来，也可以从第i-2个台阶跳两步上来。哪个花费少我们就选择从哪个跳上来。我们定义dp[i]表示到第i个台阶需要的最小花费，那么我们可以得出递推公式 dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i ...

Java 动态规划跳台阶

2022-02-18

16 1360

【数据结构和算法】青蛙跳台阶来自专栏

这题和前面 DP1 斐波那契数列基本上是一样的，不同的是，这里斐波那契数列的起始项是1,2,3,5,8，我们把它改一下即可解法一题中要求的是空间复杂度 O(1) ，很明显使用递归是行不通的，我们先改成非递归的看一下（这种复杂度也是不行的，我们先看一下代码） import java.util.S...

Java 动态规划斐波那契青蛙跳台阶

2022-02-18

8 1294

【数据结构和算法】斐波那契数列来自专栏

解法一题中要求的是空间复杂度 O(1) ，很明显使用递归是行不通的，我们先改成非递归的看一下（这种复杂度也是不行的，我们先看一下代码） import java.util.Scanner; public class Main { public static void main(Stri...

Java 动态规划斐波那契

2022-02-18

11 1872

【数据结构和算法】动态规划解最长公共子串来自专栏

动态规划解决注意这题求的是最长公共子串，不是最长公共子序列，子序列可以是不连续的，但子串一定是连续的。定义dp[i][j]表示字符串str1中第i个字符和str2种第j个字符为最后一个元素所构成的最长公共子串。如果要求dp[i][j]，也就是str1的第i个字符和str2的第j个字符为最后一个元...

java 字符串动态规划

2021-07-05

107 8592

【数据结构和算法】动态规划解最大正方形来自专栏

动态规划解决这题让求的是由1围成的最大正方形，最容易想到的一种方式就是暴力求解。解决方式就是如果某个位置是1，就以他为正方形左上角，然后沿着右边和下边找最大的正方形，并且还要保证围成的正方形中所有的数字都是1。这种虽然容易想到但代码不太好写，并且时间复杂度也比较高。下面我们来看另一种实现方式，使...

java 矩阵动态规划

2021-07-02

33 2602

【数据结构和算法】动态规划解决来自专栏

1，动态规划解决这题是让求最大的连续子序和，如果不是连续的非常简单，只需要把所有的正数相加即可。但这里说的是连续的，中间可能掺杂负数，如果求出一个最大子序和在加上负数肯定要比原来小了。解这题最简单的一种方式就是使用动态规划。我们先来了解一下动态规划的几个步骤 1，确定状态 2，找到转移公式 ...

java 动态规划

2021-04-02

7 929

【数据结构和算法】中心扩散，暴力，动态规划3种方式解决来自专栏

1，中心扩散法中心扩散法也很好理解，我们遍历字符串的每一个字符，然后以当前字符为中心往两边扩散，查找最长的回文子串，下面随便举个例子，看一下图片中我们是以每一个字符为中心，往两边扩散，来求最长的回文子串。但忽略了一个问题，回文串的长度不一定都是奇数，也可能是偶数，比如字符串&...

java 字符串动态规划

2021-04-02

144 5742

【数据结构和算法】动态规划和递归两种方式解决来自专栏

1，动态规划求解这题求的是从左上角到右下角，路径上的数字和最小，并且每次只能向下或向右移动。所以上面很容易想到动态规划求解。我们可以使用一个二维数组dp，dp[i][j]表示的是从左上角到坐标(i，j)的最小路径和。那么走到坐标(i，j)的位置只有这两种可能，要么从上面(i-1，j)走下来，要么从...

递归 java 动态规划

2021-04-02

19 1541

【数据结构和算法】动态规划和贪心算法，图文详解来自专栏

1，动态规划解决定义dp[i][0]表示第i+1天交易完之后手里没有股票的最大利润，dp[i][1]表示第i+1天交易完之后手里持有股票的最大利润。当天交易完之后手里没有股票可能有两种情况，一种是当天没有进行任何交易，又因为当天手里没有股票，所以当天没有股票的利润只能取前一天手里没有股票的利...

java 贪心算法动态规划

2021-03-21

40 2210

【数据结构和算法】递归和非递归，以及公式计算等4种实现方式来自专栏

1，递归的写法这题我们可以参照之前分析的青蛙跳台阶问题，其实原理是完全一样的我们来分析一下：当n等于1的时候，只需要跳一次即可，只有一种跳法，记f(1)=1 当n等于2的时候，可以先跳一级再跳一级，或者直接跳二级，共有2种跳法，记f(2)=2 当n等于3的时候，他可以从一级台阶上跳两步上来，也...

斐波那契数列 java 动态规划

2021-03-21

22 1351