r - 如何找到“收集最大硬币”DP 解决方案的时间复杂度？

Question

谁能帮我详细分析这个算法

检查以下链接：
https ://www.geeksforgeeks.org/collect-maximum-coins-before-hitting-a-dead-end/

这个问题有两个解决方案，第一个我认为没有 DP 是指数的，但另一个是 O(RC) 与动态编程和记忆。

其中 R 是 2D-Array 的行数，C 是列数。

我需要知道如何在数学上详细地找到这个时间复杂度 O(RC)。

标签： ralgorithmtime-complexitycomplexity-theory

Answer 1

DP 解决方案填充RxCx2表格dp，并且每个单元格dp可能被访问不超过五次 - 初始填充、此单元格的计算以及来自三个方向（上、左、右）的请求。

所以整体复杂度是O(R * C)