关于dfs with memorization的时间复杂度

最近做了一些题，有些题目可以用dp方法或者dfs with memorization来解。从leetcode的performance来看，有些时候dfs with memorization还要快一些。但是不知道具体应该如何分析这种情况下的时间复杂度，请问有人有什么心得吗？

比如说312 burst balloon，memorization方法的代码如下
public class Solution {
    public int maxCoins(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int[] vals = new int[nums.length+2];
        vals[0] = vals[vals.length-1] = 1;
        for (int i = 0; i < nums.length; i++) vals[i+1] = nums[i];
        int n = vals.length;
        int[][] memo = new int[n][n];
        return partition(vals, 0, n-1, memo);
    }

    private int partition(int[] nums, int lo, int hi, int[][] memo) { // the max when we burst baloons from lo to hi. Both indexes are exclusive
        if (hi == lo + 1) return 0;
        else if (memo[lo][hi] > 0) return memo[lo][hi];
        else {
            int res = 0;
            for (int i = lo+1; i < hi; i++) {
                res = Math.max(res, nums[lo] * nums[i] * nums[hi] + partition(nums, lo, i, memo) + partition(nums, i, hi, memo));
            }
            memo[lo][hi] = res;
            return res;
        }
    }
}

很多情况下，memoization就比bottom up的dp快呀，因为会避免算一些不需要的table entry，worst case复杂度一般是一样的

两种最坏情况的时间复杂度是一样的, 你看dp定义了多少种状态复杂度就是多少

所以判断memorization方法的复杂度还是要先以dp的思维考虑了才能总结出复杂度对吗？根本就是确定状态的个数？

metalsolid 发表于 2016-12-20 10:17
所以判断memorization方法的复杂度还是要先以dp的思维考虑了才能总结出复杂度对吗？根本就是确定状态的个数 ...

感觉有时候也要看状态转移的时候花的时间