2019年10月31日
大学里碰到的算法题，一遇动态规划就头晕。
理解没到位，就没最优解
数学建模玩的菜，动态规划难成型
今天偶遇到动态规划，是在别人电脑上看到的一本算法书，很幸运能把这个坑稍微填上一点点。
常见的动态规划解决背包问题。
主要是把背包的重量单位拆分，例如一个背包可以承重4kg。
动态规划涉及到把大问题简单化，大问题拆分，从小问题得到最优解，再扩展到大问题。这里不包括特殊条件。
4kg可以拆分成1，2，3，4kg。先得到1kg承重里能容量物体的最大价值s1。第二次放入物体，重量w，价值c：s2=c+承重(2-w)的最大价值，如果s2>s1,那么2kg的最大价值就是s2,反之s1。这里的s2并不是真的是2kg的最大价值，是一个局部最优解，最后的4kg的计算结果才是问题的最优解。 。。。。。。。。。。。。背包算法点到为止。
今天最大的收获还是画表格分析动态规划的方法。
两字符串aabce,abcaa的最大子字符串就可以用表格分析一目了然。
两个一元数组和一个两元数组能解。
