上传者: m0_52444089
|
上传时间: 2023-04-23 18:45:29
|
文件大小: 243KB
|
文件类型: DOCX
西安交通大学-算法分析作业
动态规划算法时间复杂度分析比较
数据每次从上下左右查找能拓展的数值比当前位置小的最远节点的路径,而Vis把(i,j)搜索结果最长的结果存储起来,i,j递增每次继续向下搜索时,查看是否已经有其状态了,存在直接return,没有就正常搜索,所以这样树中的每个节点均只搜索一次。所以该算法时间复杂度为O(R*C)
用例:
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9