✌更多学习资源#xff0c;可关注公-仲-hao:【阿旭算法与机器学习】#xff0c;共同学习交流~

《------往期经典推荐--…

小伙伴们好我是阿旭。

专注于人工智能AI、python、计算机视觉相关分享研究。

✌更多学习资源可关注公-仲-hao:【阿旭算法与机器学习】共同学习交流~

感谢小伙伴们点赞、关注

一、AI应用软件开发实战专栏【链接】二、机器学习实战专栏【链接】已更新31期欢迎关注持续更新中~~三、深度学习【Pytorch】专栏【链接】四、【Stable

Diffusion绘画系列】专栏【链接】

这篇文章是博主在学习动态规划系列算法过程中精心总结的42页学习笔记其中包含了动态规划的原理详解以及LeetCode中的动态规划题目汇总。

应用场景

动态规划问题的一般形式就是求最值。

动态规划其实是运筹学的一种最优化方法只不过在计算机问题上应用比较多比如说让你求最长递增子序列呀最小编辑距离呀等等。

求解动态规划的核心问题是穷举。

因为要求最值肯定要把所有可行的答案穷举出来然后在其中找最值。

动态规划特点三要素

1.最优子结构原问题的最优解所包含的子问题的解也是最优的通过子问题的最值得到原问题的最值。

2.存在重叠子问题子问题间不独立这是动态规划区别于分治的最大不同如果暴力穷举的话效率会极其低下所以需要「备忘录」或者「DP

1.分阶段将原问题划分成几个子问题。

一个子问题就是多轮决策的一个阶段它们可以是不满足独立性的。

3.做决策确定决策变量

递归是一种自顶向下的求解方式DP数组是一种自底向上的求解方式。

1.递归寻找暴力解自顶向下求解

2.通过备忘录memo优化递归过程剔除重复计算消除一下重叠子问题

table

自底向上求解主要是需要明确DP数组的含义定义然后通过递推进行推导。

DP数组注意事项

根据斐波那契数列的状态转移方程当前状态只和之前的两个状态有关其实并不需要那么长的一个

table

来存储所有的状态只要想办法存储之前的两个状态就行了。

所以可以进一步优化把空间复杂度降为

O(1)

amount问你最少需要几枚硬币凑出这个金额如果不可能凑出算法返回

状态转移方程

说明前k个硬币凑齐金额i的组合数等于前k-1个硬币凑齐金额i的组合数加上在原来i-k的基础上使用硬币的组合数。

说的更加直白一点那就是用前k的硬币凑齐金额i要分为两种情况开率一种是没有用前k-1个硬币就凑齐了一种是前面已经凑到了i-k现在就差第k个硬币了。

DP[i]

子问题:对于硬币从0到k我们必须使用第k个硬币的时候当前金额的组合数

转移方程DP[i]

https://leetcode-cn.com/problems/coin-change-2/solution/ling-qian-dui-huan-iihe-pa-lou-ti-wen-ti-dao-di-yo/

https://leetcode-cn.com/problems/coin-change-2/solution/ling-qian-dui-huan-ii-by-leetcode/

518零钱兑换2是一个组合问题DP先遍历零钱列表再遍历amount金额数

def

dp[i][j]表示t的前i个字符串可以由s的前j个字符串组成多少个

len(s)

参考https://leetcode-cn.com/problems/longest-common-subsequence/solution/dong-tai-gui-hua-zhi-zui-chang-gong-gong-zi-xu-lie/

动态规划

#dp[i][j]表示以s1的i及s2的j结尾的最长公共子串长度

#如果s1[i-1]

DFS(start_x,start_y,steps,grid)

零钱兑换1

子问题:对于硬币从0到k我们必须使用第k个硬币的时候当前金额的组合数

转移方程DP[i]

#在第二次买的时候价格其实是考虑用了第一次赚的钱去补贴一部分的

buy_1

2**j]表示这个剩余距离需要使用的最少命令数,加上已经使用的

由于返回使用的j不确定因此需要通过遍历【0k-2】确定dp[t]的最小值

dp[t]

如果当前的歌和前面的都不一样歌单前i-1首歌只包括了j-1首不同的歌曲

(N-j1)

如果不是那么就是选择之前的一首歌之前最近的K首是不能选的只能选择j-K前面的歌曲j

max(0,

欢迎关注下方GZH阿旭算法与机器学习发送【动态规划】即可获取原版文档。

欢迎小伙伴共同学习交流~