动态规划能得到一类问题的最优解，比如背包问题用动态规划来解决，怎样证明这个解就是相对应问题的最优解呢
比方说整数值的背包问题，表示状态的物品index-总容量对上有一个典范的良序（就是你枚举状态的顺序了）。假设这个算法在某个input下不对，取出最小的状态坐标，使得求解出的这个子问题答案错误。根据假设它的前继子问题都是求解正确的，带入bellman方程，它也应该被算对，矛盾。稍微一般一点的情况就是在状态的DAG上做归纳但是题主想问的应该不是这个问题，而是“怎么确认一种子问题划分和相应的状态转移方程是正确的”，这个问题就太meta了可能不太好回答。。在你设计出一个dp算法之前往往会考虑一些朴素的暴力方法，枚举原问题“完整的action序列”，优化目标是这个action序列上的可能比较复杂的某个函数。这个objective往往写成有限步的计算，所有的中间结果都是有序域\\mathbb{R}上的元素。有的时候你会发现action序列的某些部分在计算的某一部开始不再被用到了，被用到的只是这些action在之前参与的某（几）个中间计算结果。由于\\mathbb{R}上常见的操作在每个位置上都有良好的单调性，很可能能找到一组中间结果，使得我们能够枚举这种中间结果来完成原问题的优化
■网友
如何理解动态规划？基本上你可以理解为，在暴力搜索的基础上减掉了一些重复计算，从而加快速度，正确性和暴力搜索的结果是一样的，而后者由于枚举了所有可能情况，所以必然是得到最优结果的
■网友
先回顾下动态规划问题的求解过程：
（1）证明该问题具有最优子结构性质(局部最优解能决定全局最优解)；
（2）根据最优子结构，求递推方程；
（3）根据递推方程，说明该问题具有重叠子结构性质；
（4）自底向上写出求解最优值的非递归算法，同时构造最优解的解空间树；
（5）遍历解空间树，求得最优解。
贪心算法是求一个子问题的解，假设这个解是子问题的最优解，在此基础上再进一步推导更大问题的最优解。
这意味着，“贪心算法最后求出解是最优的”是基于“子问题的解的确是最优的”并且“全局最优
该局部最优解”。如果这一点不成立，那贪心最后的结果也并不可靠。
再回过头来看动态规划，由于在求解时，第一步就要求要证明最优子结构，所以保证了“全局最优
该局部最优解”。
综上，回答题主问题，是通过证明最优子结构来证明的。感觉题主有这个问题是因为很多时候大家都是说感觉这个可以dp解，然后就dp了，如果不是有必要，大家不会很严肃的推导，或者在推导递推方程的时候，很自然就承认了的确存在最优子结构这件事。
最后，随便找了个背包问题的最优子结构证明。
■网友
注意动态规划的思想核心 如果能使用动态规划解决 那么一般是将问题分解为子问题 解决子问题使用的肯定是最优策略 当所有子问题最优时可以类似递推模式 得到全局最优解
■网友
dp是遍历了一遍所有的可能路线，因此是最优解。这点是它优于贪心的地方。
so，这问题。。
【动态规划能得到一类问题的最优解，比如背包问题用动态规划来解决，怎样证明这个解就是相对应问题的最优解呢】 还是需要学习一个
推荐阅读
- 假如把中国电信监测到的3亿人一个月每天上网的所有行为打个包，哪些数据应该被提出从这些数据能得到啥
- 现在想进入智能家居行业，看了很多家，想做代理，希望得到有用的建议和意见，有行业内的内加微信聊聊吗
- 坦克|17.58万的预售价，坦克300能否得到消费者认可
- 胃酸|胃里老反酸？不妨试试这4个方法，很多人都得到了改善
- 行政复议|南京十项措施推动行政诉讼、行政复议得到快速有效解决
- 趣头条|复古外观配智慧座舱，欧拉好猫是否得到你的青睐？
- 工作一年，学农，无经验，想得到一份产品助理工作这么难
- 自学C，有如《C Primer Plus》第六版一类较经典的书推荐吗
- 淘宝淘金币和天猫积分，买家用来购物抵扣，这积分是卖家买单吗卖家得到积分又咋利用呢
- 怎样得到华为关于奖励旅游策划方案的授权