什么是动态规划，什么是背包问题

什么是动态规划，什么是背包问题

动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

它比起贪心策略，会分别算出取1、5、11的代价，从而做出一个正确决策，这样就避免掉了“鼠目寸光”！

1.3万的点赞量，讲解的非常详细： 

什么是动态规划（Dynamic Programming）？动态规划的意义是什么？ - 知乎

dp动态规划问题，有个重要的特点，

1、就是：“未来与过去无关”，这就是无后效性。

2、最优子结构；

 

DP算法的核心是，根据题目，尽可能地缩小解空间：

DP的核心思想：尽量缩小可能解空间

背包问题：

动态规划的典型例题；