动态规划

1.字符串压缩（题目较长，代码也长，有时间更新）   给你一句话，然后再给你一个字典，请把这句话中的所有单词替换成该单词在字典中的索引，不区分大小写。句子中包括",."以及空格等符号，这些符号不变，且""之中的单词不会被替换。   例子：   句子：Hello，I will go to the "New World Park".   字典：hEllo  TO  park   输出：0，I will go 1 the "New World Park".   park在""内，因此不替换。     ...

10.28晚上八点约面试，面试官跟我说部门需要Python，Shell以及少量的goland。我的语言是Java，他们部门的语言我只是简单涉猎过并不熟练。10.29线上面试。 上来就是手撕算法，三角形的最小路径，力扣原题，但是空间复杂度要求降低到O(n)。 我的思路是动态规划，自下而上遍历，同时只维护一个一维数组。 然后问了两道八股就结束了。 Python的装饰器，Linux设置定时任务，Linux看端口号的命令。

今天考试时候脑子一团浆糊，晚上刷牙时候突然开窍，有了以下思路，如有错误还请各位大神指正！   思路：从头（两个或三个数字）开始构建长城数组，逐个添加新元素到数组内，每次添加更新需要的操作次数。   /* 第二题 长城数组    长城数组 1 9 1 9, 2 5 2 5 2 5    非长城数组 2 3 1 2    给定一个数组，每次可对其中任意一数执行加1操作    问最少几次可以把它变成长城数组 */ #include <iostream> #include <vector> #define PRINT_TMP_VECTOR // 输出中间过程数组 using n...

思路：根据坐标进行dp递推而不是根据树的编号，这是关键。dp[i]代表第i个坐标之前，最大的价值（只考虑树的左右边界全包含在坐标i之前的树）。坐标从第一棵树的右边往后移动，每新包含一棵树，进行一次判断：1、新树的价值（value）小于覆盖范围内其他树的价值（dp[右边界 - 1] - dp[左边界]），则不种植该树。2、新树的价值（value）大于覆盖范围内其他树的价值（dp[右边界 - 1] - dp[左边界]），则移除其他树，种植这棵新树，更新dp[右边界]。i移到最后时，dp[终点]就是最优种植方案的价值。 #include <algorithm> #include <...

 #LeetCode[话题]#  #动态规划# 

有没有大哥帮忙看下代码啊为什么只过30%。然后就超时了不知道怎么优化了。测试用例也全过了的。   -1是钉子，珠子会左弹或者右弹， 1.第一种要素为钉子，当玩家的弹珠碰到钉子时，有可能会弹射到左下或者右下一格的位置。 2.第二种要素为得分点，当弹子经过得分点之后，可以获得得分点对应的分数。 如果当前格子不为钉子(即空白或者得分点)时，弹子会往正下方落下。 小M想知道，对于—个给定的版面，他最高可能获得多少分数。 输入 -1 0 -1 100 0 0 0 50 70 输出 50    var solutions = function(n,m,nums){ let res = -Infinity ...

原写了 Java 版本的如何求解换钱的方法数，近期进行了一些细节上的补充，以及部分错误更正，将语言换为了 C++ 语言。  基础题目 假设你现在拥有不限量的 1 元、5 元、10 元面值纸币，路人甲希望找你换一些零钱，路人甲拿出的是一张 100 元面值的纸币，试求总共有多少种换零钱的方法？ 分析：因为总共只有 3 种面值小额纸币，所以将所有可能进行枚举，直接暴力解决即可。 #include<bits/stdc++.h> using namespace std; int slove() { int ans = 0; // 10 元张数 for(int i = 0; i <= 1...

原写了 Java 版本的如何求解换钱的方法数，近期进行了一些细节上的补充，以及部分错误更正，将语言换为了 C++ 语言。  基础题目 假设你现在拥有不限量的 1 元、5 元、10 元面值纸币，路人甲希望找你换一些零钱，路人甲拿出的是一张 100 元面值的纸币，试求总共有多少种换零钱的方法？ 分析：因为总共只有 3 种面值小额纸币，所以将所有可能进行枚举，直接暴力解决即可。 #include<bits/stdc++.h> using namespace std; int slove() { int ans = 0; // 10 元张数 for(int i = 0; i <= 1...

强化学习从基础到进阶-常见问题和面试必知必答[2]：马尔科夫决策、贝尔曼方程、动态规划、策略价值迭代 1.马尔科夫决策核心词汇   马尔可夫性质（Markov property，MP）：如果某一个过程未来的状态与过去的状态无关，只由现在的状态决定，那么其具有马尔可夫性质。换句话说，一个状态的下一个状态只取决于它的当前状态，而与它当前状态之前的状态都没有关系。   马尔可夫链（Markov chain）： 概率论和数理统计中具有马尔可夫性质且存在于离散的指数集（index set）和状态空间（state space）内的随机过程（stochastic process）。   状态转移矩阵（sta...

👨‍🎓作者简介：一位喜欢写作，计科专业大二菜鸟 🏡个人主页：starry陆离 🕒首发日期：2022年8月18日星期四📚订阅专栏：『算法分析与设计』 🍁每日推荐：牛客网-面试神器如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦  @TOC  1.动态规划创始人 动态规划（Dynamic Programming, DP）由 R.Bellman（理查·贝尔曼）教授于1957年提出  Richard Ernest Bellman (1920-1984)，美国数学家，美 国艺术与科学院院士，美国工 程院院士，动态规划的创始人。  2.定义 动态规划是将多阶段决策问题进行公式化的一种技术，...

在编程的世界里，算法就像是一把把神奇的钥匙，能够开启解决各种复杂问题的大门。今天，就让我们一起走进动态规划算法这个神秘而强大的领域，看看它是如何用独特的智慧来化解难题的，并且我会用 Java 语言给大家展示它的魅力哦！一、动态规划初印象想象一下，你正站在一个巨大的迷宫面前，这个迷宫里充满了各种岔路和陷阱。如果要找到从入口到出口的最短路径，你会怎么做呢？一种笨办法就是盲目地尝试每一条可能的路线，直到找到出口为止。但这样可能会花费大量的时间和精力，因为你会在很多相同的岔路口反复徘徊。动态规划就像是一位聪明的向导，它不会像无头苍蝇一样乱撞。它会先冷静地观察迷宫的结构，把这个大问题分解成一个个小问题。...

class Solution:def spiralMatrixIII(self, rows, cols, rStart, cStart):# 初始化结果列表并将起始位置加入结果res = [(rStart, cStart)] # 如果结果列表的长度等于总的单元格数，直接返回结果 if rows * cols == 1: return res # 初始化步长和方向 step = 1 dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)] # 右、下、左、上 r, c = rStart, cStart di = 0 # 当前方向索引 # 循环直到结果列表的长度等于总的单...

    物品有限，放入多个背包，求多个背包中最小总价值的背包的最大值？1.物品具有价值m和重量属性n;2.多个背包的容量是相等的，为V；3.最后求几个背包中总价值量最小的背包，要让它的总价值量最大。// 这个该用什么方法做啊，不像是背包问题，动态规划也想不清，求大神解答！

解读题意，题目给出了一种衡量二叉树的指标：加分，该指标依赖于各个结点的权值（分数）以及二叉树的树形。各结点的权值为已知条件，而树形为未知条件，因为同一中序遍历序列可以对应多个不同的二叉树，现在问：在这诸多可能的二叉树中，哪一棵树拥有最好的指标值，它的树形又是怎样的，要求给出其指标值和前序遍历序列。 解题思路：首先，既然存在多种不同的二叉树，我们自然想要去逐一确定树形并计算对应的指标，再从中挑出最好的那一棵。那么问题来了：对于给定的中序序列，应该如何确定可能的树形？我们发现，对于中序序列，我们可以选择序列中的任一结点作为父结点（设坐标为k），在其左边的序列，可以独立地作为左子树序列，右边的序列则...

本文章用于自我总结和帮助他人，总体上来说这是一个“编辑距离”的变种题，需要2维DP。题目是这样的： 英文单词拼写的时候可能会出现拼写错误的情况(typo)。下面的题目，我们尝试实现拼写纠错推荐的功能。 字串编辑距离是衡量字串间相似度的常见手段。 ①字串编辑距离：是指利用字符操作，把字符串A转换成字符串B所需要的最少操作数。 ②字串操作包括：删除字符(removal)、插入字符(insertion)、修改字符(substitution)。 ③使用以下规则对推荐纠错选项进行相似度排序。得分越高，认为相似度越低 只涉及到26个英文字符、不区分大小写。 删除(removal) 3分 插入(insert...

已知 15 个可选的频带，如何选出 N 个频带使和的四舍五入误差最小？以0号频带为例，频带的数据类似这样：误差公式：求使得四舍五入误差最小的频带组合。有没有思路什么的？

#include <bits/stdc++.h> //动态规划的思想用存储前面计算过的东西，加以利用 //完全平方数可以多次使用，类似完全背包，正好等于n的时候的用值最少 using namespace std; #define N (int)(1e4+5) int dp[N]; //体积为完全平方数的值 int volume[N]; //价值全部为1 int my_min(int a,int b){ return (a<b)?a:b; } //正序 int main(){ int n,v; scanf("%d",&n); v=(int)sqrt(...

#include <bits/stdc++.h> using namespace std; #define N (int)(1e3+5) int dp[N]; int dp2[N]; int value[N],volume[N]; int my_max(int a,int b){ return (a>b)?a:b; } int main(){ int n,V; scanf("%d %d",&n,&V); for(int i=0;i<n;i++){ scanf("%d %d",&volume[i],&...