佛说wh

分类

/ 注册

全部文章（共19篇）

题解 | #矩阵的最小路径和#

2022.0816算法第31题矩阵的最小路径和一样的套路，动态规划问题，相当于对路的方案数进行加权。 1、状态矩阵dp 为到达i，j位置的最小路径和 vector<vector<int>> dp=matrix; 2、初始值将边界的值进...

C++ 动态规划

2022-08-16

0 261

题解 | #不同路径的数目(一)#

2022.0816算法第30题不同路径的数目(一) 动态规划问题，也能使用递归，感觉动态规划和递归是互通的，应为有状态转移方程存在。 1、状态矩阵 vector<vector<int>> dp(m,vector<int>(n,1)); 2...

动态规划 C++

2022-08-16

0 242

题解 | #最长上升子序列(一)#

2022.0816算法第29题最长上升子序列(一) 子序列不好使用暴力解法，主要是子序列的方案太多了。采用动态规划进行求解。 1、状态矩阵dp 存储子序列末尾位置的最大长度，并且初始化为1. vector<int> dp(arr.size(),1)...

C++ 动态规划

2022-08-16

0 412

题解 | #连续子数组的最大和#

2022.0816算法第28题连续子数组的最大和连续子数组和组合需要两层循环，分别确定起点和终点如果是子序列的话，可能性就多了动态规划求解， 1、状态矩阵dp 记录每个子数组结束位置的最大和。 vector<int> dp(array.s...

C++ 动态规划

2022-08-16

0 250

题解 | #最长公共子串#

2022.0815算法第26题最长公共子串这个和最长公共子序列采用的方法是一样的，需要构造状态矩阵，记录当前的子串状态。主要在于获取最长子串的位置，用于分割子串。可以记录最长子串的长度和最长子串出现的最后的索引位置。这点需要使用两个变量 int maxL...

动态规划 C++ 字符串

2022-08-15

0 264

题解 | #最小花费爬楼梯#

2022.0815算法第25题最小花费爬楼梯这个方法也是要找到递推关系式， res[i]=min(res[i-1]+cost[i-1],res[i-2]+cost[i-2]); 感觉这个和高中求数列是十分相似的，有初始值，有递推公式，这样也可以求出来通项计算机则直接可以通过循环进...

动态规划 C++

2022-08-15

0 285

题解 | #跳台阶#

2022.0815算法第24题跳台阶这个解决方法和斐波那契数列一样，知识初始值不同。但是最主要的是想到使用这个方法进行求解。感觉这类问题都是需要找到状态转移方程，也就是状态数列的n和状态n-1等的关系。递推公式就是这样， int a =&nbs...

C++ 动态规划

2022-08-15

0 245

题解 | #斐波那契数列#

2022.0815算法第23题斐波那契数列动态规划dynamic programing的入门级题目。可以从后往前，也可以从前往后从后往前需要递归，从后往前需要循环。从后往前的代码： vector<int> res(n+1); res[1]=1...

C++ 动态规划

2022-08-15

0 236

题解 | #最长公共子序列(二)#

2022.0814算法第21题最长公共子序列(二) 动态规划问题，但是做的比较少还没有理解动态规划的主要套路。这个需要先求解一个二维矩阵，求解出最长子序列的长度，然后根据指示方向取出最长子序列。第一步需要求解最长子序列长度，并记录当前字符的方向，也就是最长子序列的取值位置方向。...

动态规划 C++

2022-08-14

1 436