算法<初级> - 第五章 递归与动规相关问题（完结）
2021-02-17 15:20
阅读：653
-
暴力递归跟上述一样，return的不是true/false而是价值，可变参数仍然是遍历i与重量cost
-
动态规划跟上题类似，转为二维表，[][]表示可以添加的最大价值，从最后开始往前状态转移 - [bag]后都是int系统最小值(相当于负值)，而[i]值处都是0，相当于已经把物体都处理完成了，没有其他价值可以加进来了。 - 往前每遍历一个都在[][]赋值其价值，分为取跟不取。
-
无后效性：能改成动态规划的重要性质，存在空间换时间的解，怎么到子状态的路径不影响子状态的返回值。eg. dp[3][3]可能有多种到此的情况，但是前面的不同路径并不影响dp[3][3]的返回值结果。
-
分析可变参数(解空间大小) - 需要得到的结果/值直接作为返回值而不是作为可变参
-
确定最终状态 - 要返回的状态
-
根据basecase确定初始状态 - 边界条件
-
确定普遍位置依赖的状态转移函数
-
文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：算法<初级> - 第五章 递归与动规相关问题（完结）
文章链接：http://soscw.com/index.php/essay/56630.html
文章标题：算法<初级> - 第五章 递归与动规相关问题（完结）
文章链接：http://soscw.com/index.php/essay/56630.html
评论
亲，登录后才可以留言！