动态规划如何解决0问题？

本文共计2544个文字，预计阅读时间需要11分钟。

动态规划解0-1背包问题+动态规划解0-1背包问题是一个典型的动态规划案例，我查阅了众多相关资料，但大部分内容都比较深奥难懂，不适合初学者。其中涉及的递推关系、填表等内容，对于刚接触算法的小白来说，理解起来有一定难度。

动态规划解0-1背包问题

动态规划解0-1背包问题是一个十分典型案例，我从网上查询好多相关资料，但是大部分都深奥难懂，并不适合初学算法的小白，其中涉及的递推关系式、填表，以及最后的二维表简化为一维表的优化过程，好多都是一笔带过，所以，今天就尽我所能，来叙述一下对于0-1背包问题使用动态规划来求解。
要解决0-1背包问题，首先咱们要解决的是什么是动态规划。

动态规划

先说一说什么是动态规划。
动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
这里又涉及到分治算法，那就简单概述一下分治算法。
分治算法简而言之就是将一个大问题分成若干个小问题，通过求解小问题的最优解，进而推出所求解问题的最优解。
这么乍一看，可能会觉得分治算法与动态规划相类似，实际上，他们有一个最本质的区别，那就是子问题的类型不同。
分治算法的子问题是相互独立的，子问题与子问题之间并没有什么关联。而动态规划的子问题就有意思了，他们是重叠的子问题。