4道动态规划题

[qjkobe]

动态规划

动态规划问题是笔试常见题，看似很难，但其实只要多训练，就会发现这些题其实都有套路。据说小学生编程训练就已经做到动态规划了呢。 以下四道动态规划题选自leetcode中文社区中级算法动态规划一章。

跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例1

输入：[2,3,1,1,4]
输出：true
解释：从位置0到1跳1步，然后跳3步到达最后一个位置。

示例2

输入：[3,2,1,0,4]
输出：false
解释：无论怎样，你总会到达索引为3的位置，但该位置的最大跳跃长度是0。所以你永远不可能到达最后一个位置。

不同路径

一个机器人位于一个m x n网格的左上角（起始点在下图中标记位“Start”）。
机器人每次只能向下或者向右移动一步。机器人试图到达网格的右下角（在下图中标记位“Finish”）。
问总共有多少条不同的路径？

例如，上图是一个7 x 3 的网格。有多少可能的路径？
说明： m和n的值均不超过100。
示例1：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有3条路径可以到达右下角。
1. 向右 - 向右 - 向下
2. 向右 - 向下 - 向右
3. 向下 - 向右 - 向右

示例2：

输入：m = 7, n = 3
输出：28

零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回-1。
示例1：

输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1

示例2：

输入：coins = [2], amount = 3
输出：-1

说明：
你可以认为每种硬币的数量是无限的。

Longest Increasing Subsequence这题它没翻译

给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例：

输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明：

• 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
• 你算法的时间复杂度应该为 O(n2) 。
  进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗？

[qjkobe]

跳跃游戏

思路比较简单的动态规划。

    //J[i]表示能否到达i
    //i=0:true
    static boolean canJump(int[] nums) {
        boolean[] J = new boolean[nums.length];
        J[0] = true;
        for (int i = 0; i < nums.length; i++) {
            if (J[i]) {
                for (int j = i + 1; j < nums.length && j <= i + nums[i]; j++) {
                    J[j] = true;
                }
            }
        }
        return J[nums.length - 1];
    }

    public static void main(String[] args) {
        int nums1[] = {2, 3, 1, 1, 4};
        int nums2[] = {3, 2, 1, 0, 4};
        System.out.println(canJump(nums1));
        System.out.println(canJump(nums2));
    }

有种贪心算法复杂度只有O(n)

    static boolean canJump2(int[] nums) {
        int leftCanJumpIndex = nums.length - 1;
        //假设最后一个点可以跳到。只要找到能跳到这个点的最靠左的一个点就行。
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] + i >= leftCanJumpIndex) {
                leftCanJumpIndex = i;
            }
        }
        return leftCanJumpIndex == 0;
    }

[qjkobe]

不同路径

因为每个格子只能由左边和上方的走到，所以他的路径数就等于左边和上方的路径之和。

    static int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        dp[0][0] = 1;
        //边界都只有一种
        for (int i = 1; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i < n; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                //因为只有两条边可以走过来。所以就是等于那两个格子的步数
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }

    public static void main(String[] args) {
        System.out.println(uniquePaths(3, 2));
        System.out.println(uniquePaths(7, 3));
    }

[qjkobe]

零钱兑换

带备忘录的递归算法。递推关系很简单。就是amount减去当前的coin，看看能否组成。如果可以的话，取最小的方案。

    static int[] memo;
    static int coinChange(int[] coins, int amount) {
        memo = new int[amount+1];
        return coinChangeHelper(coins, amount);
    }
    static int coinChangeHelper(int[] coins, int amount) {
        if (amount == 0) {
            return 0;
        }
        if (memo[amount] != 0) {
            return memo[amount];
        }
        int min = Integer.MAX_VALUE;
        for (int a : coins) {
            if (a > amount) {
                continue;
            }
            if (a == amount) {
                return 1;
            }
            int res = coinChangeHelper(coins, amount - a);
            if (res == -1) {
                continue;
            } else {
                min = Math.min(min, res + 1);
            }
        }
        memo[amount] = min == Integer.MAX_VALUE ? -1 : min;
        return memo[amount];
    }

动态规划。一样是根据递推关系。但是是从小往大走，所以没有递归栈的烦恼。

    static int coinChange(int[] coins, int amount) {
        if (amount == 0) {
            return 0;
        }
        //dp[i]表示i金额最少需要多少硬币
        int[] dp = new int[amount + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = amount + 1;
        }
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int a : coins) {
                if (a <= i) {
                    //如果硬币比金额小。那就是金额减去硬币的dp+1。取最小的方案
                    dp[i] = Math.min(dp[i], dp[i - a] + 1);
                }
            }
        }
        if (dp[amount] == amount+1) {
            return -1;
        }
        return dp[amount];
    }

[qjkobe]

Longest Increasing Subsequence

这个动态规划有点绕。感觉还是要多练习。虽然是一维的，但是因为转移方程比较蛋疼，很容易写错。

    static int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        //dp[i]表示i下标为止最大上升子序列长度。
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int maxdp = 1;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            for(int j =0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    if (dp[i] > maxdp) {
                        maxdp = dp[i];
                    }
                }
            }
        }
        return maxdp;
    }


    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println(lengthOfLIS(nums));
        int[] nums2 = {10,9,2,5,3,7,101,18};
        System.out.println(lengthOfLIS(nums2));
        int[] nums3 = {1, 5, 1, 2, 1, 2, 3};
        System.out.println(lengthOfLIS(nums3));

        int[] nums4 = {1, 3, 5, 1, 2, 7, 3, 4, 5};
        System.out.println(lengthOfLIS(nums4));

    }

二分查找的动态规划。复杂度O(nlogn)比上面的算法快不少。主要是维护一个有序的表，详见注释。

    static int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        //maxRight[i]表示上升子序列长度为i时的最后一位的值。（尽可能小）
        int[] maxRight = new int[nums.length];
        int maxRightLength = 0;
        for (int i = 0; i < nums.length; i++) {
            int lo = 0, hi = maxRightLength;
            int mid;
            while (lo < hi) {
                mid = (lo + hi) / 2;
                if (nums[i] > maxRight[mid]) {
                    lo = mid + 1;
                } else {
                    hi = mid;
                }
            }
            //循环跳出的时候，此时的下标表示nums[i]大于maxRight[lo-1]但要小于maxRight[lo]。根据尽量小原则，用这个替换掉maxRight[lo]
            maxRight[lo] = nums[i];
            if (maxRightLength == hi) {
                //hi没有变化说明nums[i]大于所有的，就加到最后面。
                maxRightLength++;
            }

        }
        return maxRightLength;
    }