动态规划
0 人感兴趣 · 61 次引用
- 最新
- 推荐
05. 机器学习入门 1 - 动态规划
咱们之前的课程就给大家讲了什么是人工智能，也说了每个人的定义都不太一样。关于人工智能的不同观点和方法，其实是一个很复杂的领域，我们无法用一个或者两个概念确定什么是人工智能，无法具体化。
ARTS 打卡 第三周
A：62. 不同路径 R： GenAI 十大热门技能 T： Pandas解析Json S：工作强度太大了，我哪里还有时间健身，锻炼？
LCR 089. 打家劫舍
动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。
javaScript 实现动态规划 (Dynamic Programming)01 背包问题
动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。
【牛客刷题 - 算法】NC7 买卖股票的最好时机 (一)
描述假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益 你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天
头脑风暴：打家劫舍 2
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
leetcode 53. Maximum Subarray 最大子数组和 (中等)
定义一个max保存遍历过程中出现的最大子数组和，也是返回结果，定义一个dp[i]，用来表示以第i个元素为结尾的数组的最大数组和。
leetcode 10. Regular Expression Matching 正则表达式匹配 (困难)
定义一个二维数组dp，其中dp[i][j]表示字符串s的子串s[0, i]是否可以被字符串p的子串p[0,j]匹配，根据正则表达式的不同情况，即星号、点号、非星号点号的字符，我们可以分情况讨论来更新dp数组。
leetcode 72. Edit Distance 编辑距离 (中等)
使用一个二维数组dp[i][j]，表示将第一个字符串到位置i为止，和第二个字符串到位置j为止，最多需要几步编辑。
leetcode 121 Best Time to Buy and Sell Stock 买卖股票的最佳时机 (简单)
遍历一次数组，在每个位置i时，记录i位置之前所有价格中的最低价格，然后将当前价格作为售出价格，查看当前收益是不是最大收益即可。
leetcode 650. 2 Keys Keyboard 只有两个键的键盘 (中等)
还是动态规划，这里需要乘除法来计算位置，因为粘贴操作是位数增加的。我们使用一个一维数组dp，其中位置i表示延展到长度i的最少操作次数。
leetcode 322. Coin Change 零钱兑换 (中等)
每个硬币可以用无限多次，所以是完全背包问题。dp[i]表示，达到总金额i所需的最少硬币数，因为求最少硬币数所以先将dp初始化为amount+2，状态转移方程为：dp[i] = min(dp[i], dp[i-coin] + 1)
leetcode 474. Ones and Zeroes 一和零 (中等)
这道题也是一个背包问题，背包问题：有N个物品和容量为W的背包，每个物品都有自己的体积w和价值v，求拿哪些物品可以使得背包所装下物品的总价值最大。如果限定每种物品只能选择0个或1个，则问题称为0-1背包问题；
leetcode 416. Partition Equal Subset Sum 分割等和子集 (中等)
设所有数字和为sum，我们的目标是选取一个子数组，使它的总和为sum/2，定义二维boolean数组dp[i][j]，其意义是使用前i个数字的和能不能构成整数j。
leetcode 1143. Longest Commom Subsequence 最长公共子序列 (中等)
使用动态规划来解决本题，定义一个二维数组dp，其中dp[i][j]表示到第一个字符串位置i为止、到第二个字符串位置j为止、最长的公共子序列长度。这样一来我们就可以很方便地分情况讨论这两个位置对应的字母相同中与不同的情况了。
leetcode 300. Longest Increasing Subsequence 最长递增子序列 (中等)
核心思想是使用一个数组dp来保存，dp[i]的意义是到该位置为止的最长递增子序列。最后求所有位置的最大值，而不是dp的最后元素。
leetcode 139. Word Break 单词拆分 (中等)
这道题的分割条件由集合内的字符串决定，因此在考虑每个分割位置时，需要遍历字符串集合，以确定当前位置是否可以成功分割，注意对于位置0，需要初始化值为真。
leetcode 279. Perfect Squares 完全平方数 (中等)
动态规划，dp[i]表示i有几个完全平方数的加和构成，枚举比i小的完全平方数，状态转移方程为dp[i] = min(dp[i-k] + 1) ，k就是完全平方数
leetcode 221. Maximal Square 最大正方形 (中等)
使用动态规划来解决，使用dp[i][j]表示以(i,j)为右下角，且只饮食1的正方形的边长最大值。如果我们能计算出所有dp[i][j]的值，那么其中的最大值即为矩阵中只饮食1的下方形的边长最大值，其平方即为最大下方形的面积。
leetcode 542. 01 Matrix 01 矩阵 (中等)
判断使用动态规划思路解决问题，先定义一个数组dp[][]来，找到状态转移方程式。本题需要从左上开始搜索一次，右下开始搜索一次。
leetcode 64. Minimum Path Sum 最小路径和 (中等)
二维的动态规则，定义一个二维dp数组，其中dp[i][j]表示从左上角开始到(i, j)位置的最优路径的数字和。因为每次只能向下或者向右移动，我们可以得到状态转移方程dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。
算法: 动态规划 - 斐波那契数列问题
LeetCode 509：斐波那契数 （通常用 F(n) 表示）形成的序列称为斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给定 n ，请计算 F(n) 该问题。
