leetcode组合总和 Ⅳ 解题路径

题目：

关于动态规划类题目的思路如何找在上一篇博客 https://www.cnblogs.com/niuyourou/p/11964842.html 讲的非常清楚了，该博客也成为了了leetcode中戳气球题目点赞和阅读最多的题解（虽然题解本身就很少）。

本题的解题路径与上述博客一致，也是从递归到分治到 动态规划。

各个解法之间的过渡不再赘述，有兴趣的朋友可以看看我的上述博客。https://www.cnblogs.com/niuyourou/p/11964842.html

这次我们只贴关键代码供各位参考：

递归搜索解法：

  /**

     * @Author Nxy

     * @Date 2019/12/21

     * @Param

     * @Return

     * @Exception

     * @Description 递归搜索

     */

    int i = 0;

    public int combinationSum4(int[] nums, int target) {

        if (nums == null) {

            return 0;

        }

        combinationSum4(nums, 0, target);

        return i;

    }

    public void combinationSum4(int[] nums, int beforeRe, int target) {

        if (beforeRe > target) {

            return;

        }

        if (beforeRe == target) {

            i++;

            return;

        }

        int length = nums.length;

        for (int i = 0; i < length; i++) {

            int tempRe = beforeRe + nums[i];

            combinationSum4(nums, tempRe, target);

        }

    }

分治解法：

状态转移方程：dp[i] = sum{ dp[i - num] for num in nums and if i >= num }

    /**

     * @Author Nxy

     * @Date 2019/12/21

     * @Param

     * @Return

     * @Exception

     * @Description 分治加缓存

     */

    public int combinationSum4II(int[] nums, int target) {

        if (nums == null) {

            return 0;

        }

        int length = nums.length;

        Map<Integer, Integer> cache = new HashMap<Integer, Integer>();

        return combinationSum4II(nums, target, length, cache);

    }

    public int combinationSum4II(int[] nums, int target, int length, Map<Integer, Integer> cache) {

        if (target < 0) {

            return 0;

        }

        if (target == 0) {

            return 1;

        }

        Set s = cache.keySet();

        if (s.contains(target)) {

            return cache.get(target);

        }

        int temp = 0;

        for (int i = 0; i < length; i++) {

            temp += combinationSum4II(nums, target - nums[i], length, cache);

        }

        cache.put(target, temp);

        return temp;

    }

从递归到分治的效率提升：

动态规划解法：

/**

    *   @Author Nxy

    *   @Date 2019/12/21

    *   @Param

    *   @Return

    *   @Exception

    *   @Description DP解法

    */

    public int combinationSum4III(int[] nums, int target){

        if(nums==null){return 0;}

        int length=nums.length;

        int[] cache=new int[target+1];

        cache[0]=1;

        for(int i=1;i<=target;i++){

            int temp=0;

            for(int j=0;j<length;j++){

                if(i-nums[j]==0){

                    temp++;

                    continue;

                }

                if(i-nums[j]>0){

                    temp+=cache[i-nums[j]];

                }

            }

            cache[i]=temp;

        }

        return cache[target];

    }

效率提升：

递归太费时，我们单独看下分治到动态规划的效率提升：

巴特西

leetcode组合总和 Ⅳ 解题路径

最新文章

热门文章