DP – Algorithms and Leetcode – Medium
什么情况下使用动态规划
满足下面三个条件之一，则极有可能使用动态规划 90% — 95%：
- 求最大值，最小值
- 判断是否可行
- 统计方案个数
极不可能使用动态规划的情况：
- 求出所有具体的方案而非方案的个数,要用DFS而不是DP(99%不用DP), 除了N皇后
- 输入数据是一个集合而不是序列,输入数据是一个集合而非序列(70~80%不用DP)，除了背包问题
- 暴力的算法已经是多项式级别, 本来时间复杂度就在O(n^{2})或者O(n^{3})的问题继续优化,因为不怎么能优化…(100%不用DP)• 动态规划擅长与优化指数级别复杂度(2^n,n!)到多项式级别复杂度(n²,n³), 不擅长优化n³到n²
Read full article from DP – Algorithms and Leetcode – Medium
No comments:
Post a Comment