赞
踩
动态规划总结:动态规划中每一个状态一定是由上一个状态推导出来的
判断什么时候使用回溯,什么时候使用动态规划
动态规划五部曲
对于我来说,我觉得可以根据题目要求来先举例子、画图、利用例子来推导出递推公式。如果举例子后找不出规律,那么就试试数学的假设思维【力扣334、96】
并且定义的数组的含义基本都是从初始到i这个范围里的所有结果。就是dp[i]是一定是包含了他上一个阶段的所有结果。
动态规划之背包问题:
01背包:动态规划题型——0-1背包_相合_vinegar的博客-CSDN博客
完全背包:动态规划题型——完全背包_相合_vinegar的博客-CSDN博客
题目:
Day2:53最大子数和
Day4:509斐波那契数
Day8:118杨辉三角
Day9:119杨辉三角 II
Day10:121买卖股票的最佳时机
Day23:292Nim 游戏
Day25:441排列硬币
爬楼梯问题:
Day4:70爬楼梯
Day71:746使用最小花费爬楼梯
路径问题:
Day71:62不同路径
Day71:63不同路径 II
Day81:64最小路径和
数学思维问题:
Day72:96不同的二叉搜索树
Day72:343整数拆分
Day76:357统计各位数字都不同的数字个数
Day81:396旋转函数
01背包问题:
Day73:416分割等和子集
Day73:474一和零
Day73:494目标和
Day74:1094最后一块石头的重量 II
完全背包问题
Day74:518零钱兑换 II
Day74:322零钱兑换
Day74:377组合总和 Ⅳ
Day75:279完全平方数
Day75:139单词拆分
子序列问题——动态规划思想是希望连续的,也就是说上一个状态和下一个状态(自变量)之间有关系而且连续。有序列、子xx的字眼——eg序列、子序列、子数组、子字符串的问题就是动态规划
Day76:300最长递增子序列
Day77:674最长连续递增序列
Day77:718最长重复子数组
Day77:1143最长公共子序列
子序列中的编辑距离问题——见过的很多2个串的题,大部分都是dp[i][j]分别表示s串[0...i]和t串[0...j]怎么怎么样然后都是观察s[i]和t[j]分等或者不等的情况而且方程通常就是dp[i-1][j-1]要么+要么||dp[i-1][j] 类似的
Day77:1143最长公共子序列
Day78:115不同的子序列
Day78:392判断子序列
Day78:583两个字符串的删除操作
Day78:1035不相交的线
Day79:72编辑距离
子序列中的回文问题——
Day79:516最长回文子序列
Day43:647回文子串(动态规划法的做法在Day80)
打家劫舍问题——
Day79:198打家劫舍
Day80:213打家劫舍 II
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。