算法练习（11）：牛客在线编程07 动态规划

「爱情、让人受尽委屈。」 2024-02-24 00:53 113阅读 0赞

package jz.bm;
    
    import javax.crypto.MacSpi;
    import java.util.ArrayList;
    import java.util.Arrays;
    
    public class bm7 {
        
        /**
         * BM62 斐波那契数列
         */
        public int Fibonacci(int n) {
        
            if (n <= 2) {
        
                return 1;
            }
            int[] dp = new int[n + 1];
            dp[1] = 1;
            dp[2] = 1;
            for (int i = 3; i <= n; i++) {
        
                dp[i] = dp[i - 1] + dp[i - 2];
            }
            return dp[n];
        }
    
        /**
         * BM63 跳台阶
         */
        public int jumpFloor (int number) {
        
            int[] dp = new int[number + 1];
            dp[0] = 1;
            dp[1] = 1;
            for (int i = 2; i <= number; i++) {
        
                dp[i] = dp[i - 2] + dp[i - 1];
            }
            return dp[number];
        }
    
        /**
         * BM64 最小花费爬楼梯
         */
        public int minCostClimbingStairs (int[] cost) {
        
            int[] dp = new int[cost.length + 1];
    //        dp[1] = 0; //只有一层已经在顶楼了
    //        dp[2] = 0; //两层的话选择从2楼开始
            for (int i = 2; i <= cost.length; i++) {
        
                dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
            }
            return dp[cost.length];
        }
    
        /**
         * BM65 最长公共子序列(二)
         */
        public String LCS (String s1, String s2) {
        
            if (s1 == null || s1.equals("") || s2 == null || s2.equals("")) {
        
                return "";
            }
            int m = s1.length(), n = s2.length();
            String[][] dp = new String[m + 1][n + 1]; //dp[i][j]表示从左到右，当处理到s1的第i个元素和s2的第j个元素时的公共子序列
            for (int i = 0; i <= m; i++) {
        
                dp[i][0] = "";
            }
            for (int i = 0; i <= n; i++) {
        
                dp[0][i] = "";
            }
            for (int i = 1; i <= m; i++) {
        
                for (int j = 1; j <= n; j++) {
        
                    if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
        
                        dp[i][j] = dp[i - 1][j - 1] + s1.charAt(i - 1);
                    } else {
        
                        //取长度较长的情况
                        dp[i][j] = dp[i - 1][j].length() > dp[i][j - 1].length() ? dp[i - 1][j] : dp[i][j - 1];
                    }
                }
            }
            return dp[m][n].equals("") ? "-1" : dp[m][n];
        }
    
        /**
         * BM66 最长公共子串
         */
        public String LCS66 (String str1, String str2) {
        
            if (str1 == null || str1.equals("") || str2 == null || str2.equals("")) {
        
                return "";
            }
            int max = 0; //每段子串都是断开的，记录最长的那一个
            int maxIndex = 0;
            int m = str1.length(), n = str2.length();
            int[][] dp = new int[m + 1][n + 1]; //dp[i][j]表示从左到右，当处理到s1的第i个元素和s2的第j个元素时的公共字串长度
            for (int i = 1; i <= m; i++) {
        
                for (int j = 1; j <= n; j++) {
        
                    if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
        
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                        if (dp[i][j] > max) {
        
                            max = dp[i][j];
                            maxIndex = i;
                        }
                    } else {
        
                        dp[i][j] = 0; //无法构成字串
                    }
                }
            }
            return str1.substring(maxIndex - max, maxIndex);
        }
    
        /**
         * BM67 不同路径的数目(一)
         */
        public int uniquePaths (int m, int n) {
        
            int[][] dp = new int[m + 1][n + 1];
            for (int i = 1; i <= m; i++) {
        
                for (int j = 1; j <= n; j++) {
        
                    //只有一行或一列时，只有一张方法
                    if (i == 1) {
        
                        dp[i][j] = 1;
                        continue;
                    }
                    if (j == 1) {
        
                        dp[i][j] = 1;
                        continue;
                    }
                    //只能来自于上或者右
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
            return dp[m][n];
        }
    
        /**
         * BM68 矩阵的最小路径和
         */
        public int minPathSum (int[][] matrix) {
        
            int row = matrix.length;
            int col = matrix[0].length;
            int[][] dp = new int[row][col];
            //初值
            dp[0][0] = matrix[0][0];
            for (int i = 1; i < row; i++) {
        
                dp[i][0] = dp[i - 1][0] + matrix[i][0];
            }
            for (int i = 1; i < col; i++) {
        
                dp[0][i] = dp[0][i - 1] + matrix[0][i];
            }
            for (int i = 1; i < row; i++) {
        
                for (int j = 1; j < col; j++) {
        
                    //选择值最小的路径
                    dp[i][j] = Math.min(dp[i - 1][j] + matrix[i][j], dp[i][j] + matrix[i][j]);
                }
            }
            return dp[row - 1][col - 1];
        }
    
        /**
         * BM69 把数字翻译成字符串
         */
        public int solve (String nums) {
        
            if (nums == null | "".equals(nums) || nums.startsWith("0")) {
        
                return 0;
            }
            int n = nums.length();
    //        for (int i = 1; i < n; i++) {
        
    //            if (nums.charAt(i) == '0' && !(nums.charAt(i - 1) == '1' || nums.charAt(i - 1) == '2')) {
        
    //                return 0;
    //            }
    //        }
            int[] dp = new int[n + 1];
    //        Arrays.fill(dp, 1);
            dp[0] = 1;  //默认一个才行
            dp[1] = nums.charAt(0) == '0' ? 0 : 1;
            for (int i = 2; i <= n; i++) {
        
                //无法独立编码也无法组合编码 00 或者 30 ，40 ...
                if(nums.charAt(i-1) == '0' && (nums.charAt(i-2) == '0' || nums.charAt(i-2) > '2')){
        
                    return 0;
                    //只能组合编码
                }else if(nums.charAt(i-1)=='0'){
         //10,20
                    dp[i] = dp[i-2];
                    //只能独立编码
                }else if(nums.charAt(i-2)=='0' || nums.charAt(i-2)>'2' || nums.charAt(i-2)=='2'&& nums.charAt(i-1)>'6' ){
         //0x,超过27
                    dp[i] = dp[i-1];
                    //两种编码方式都可以
                }else{
        
                    dp[i] = dp[i-1]+dp[i-2];
                }
    //            int num = (nums.charAt(i - 2) - '0') * 10 + nums.charAt(i - 1) - '0';
    //            if ((num >= 11 && num <= 19) || (num >= 21 && num <= 26)) { //可以组合又可以单独译码
    //                dp[i] = dp[i - 1] + dp[i - 2];
    //            } else { //只能单独破译或者是10，20
    //                dp[i] = dp[i - 1];
    //            }
            }
            return dp[n];
        }
    
        /**
         * BM70 兑换零钱(一)
         */
        public int minMoney (int[] arr, int aim) {
        
            int[] dp = new int[aim + 1];
            //初值，都设为最大值，假设货币值1元，则最大数为aim，因此可以设置为aim + 1
            Arrays.fill(dp, aim + 1);
            dp[0] = 0;
            for (int i = 1; i <= aim; i++) {
        
                //枚举所有的面值，找到最小值
                for (int j = 0; j < arr.length; j++) {
        
                    if (i - arr[j] >= 0) {
         //当前面值可用
                        dp[i] = Math.min(dp[i], dp[i - arr[j]] + 1);
                    }
                }
            }
            return dp[aim] > aim ? -1 : dp[aim];
        }
        /**
         * BM71 最长上升子序列(一)
         */
        public int LIS (int[] arr) {
        
            int m = arr.length;
            if (m == 0) {
        
                return 0;
            }
            int[] dp = new int[m]; //以i为结尾的最长子序列
            //初值都设置1，每个数字都是一个序列
            Arrays.fill(dp, 1);
            int res = 1;
            for (int i = 1; i < m; i++) {
        
                //遍历之前的所有数字，找到子序列
                for (int j = 0; j < i; j++) {
        
                    //小于结尾数字，序列长度加1
                    if (arr[i] > arr[j]) {
        
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
                res = Math.max(dp[i], res);
            }
            return res;
        }
    
        /**
         * BM72 连续子数组的最大和
         */
        public int FindGreatestSumOfSubArray (int[] array) {
        
            int n = array.length;
            int[] dp = new int[n + 1];
            dp[0] = 0;
            int max = array[0];
            for (int i = 1; i <= n; i++) {
        
                dp[i] = Math.max(dp[i - 1] + array[i - 1], array[i - 1]);
                max = Math.max(max, dp[i]);
            }
            return max;
        }
    
        /**
         * BM73 最长回文子串
         */
        public int getLongestPalindrome (String A) {
        
            int maxlen = 1;
            for(int i = 0; i < A.length() - 1; i++)
                maxlen = Math.max(maxlen, Math.max(getPalindrome(A, i, i), getPalindrome(A, i, i + 1)));
            return maxlen;
        }
        public int getPalindrome(String A, int left, int right) {
        
            while (left >= 0 && right < A.length() && A.charAt(left) == A.charAt(right)) {
        
                left--;
                right++;
            }
            //注意：长度要减1
            return right - left - 1;
        }
    
        /**
         * BM74 数字字符串转化成IP地址
         */
        //递归回溯
        public ArrayList<String> restoreIpAddresses (String s) {
        
            ArrayList<String> res = new ArrayList<>();
            dfs(s, 0, res, new ArrayList<String>());
            return res;
        }
        private void dfs(String s, int begin, ArrayList<String> res, ArrayList<String> cur) {
        
            //找到4段IP，并且字符串遍历完毕
            System.out.println(cur.size());
            if (cur.size() == 4 && begin == s.length()) {
        
                res.add(cur.get(0) + "." + cur.get(1) + "." + cur.get(2) + "." + cur.get(3));
                return;
            }
            //最多需要3 * （4 - cur.size())数字,最少需要（4 - cur.size()数字
            if ((s.length() - begin > 3 * (4 - cur.size())) || (s.length() - begin < (4 - cur.size()))) {
        
                return;
            }
            //寻找1到3位数字，作为当前的ip段
            for (int i = begin; i < begin + 3 && i < s.length(); i++) {
        
                String s1 = s.substring(begin, i + 1);
                int num = Integer.parseInt(s1);
                //小于255且不能有前导0
                if (num >= 0 && num <= 255 && (s1.length() == 1 || s1.charAt(0) != '0')) {
        
                    cur.add(s1);
                    dfs(s,i + 1, res, cur);
                    cur.remove(cur.size() - 1);
                }
            }
        }
    
        /**
         * BM75 编辑距离(一)
         */
        public int editDistance (String str1, String str2) {
        
            int m = str1.length(), n = str2.length();
            int[][] dp = new int[m + 1][n + 1];//以i，j为结尾的字符串str1和str2，最少操作数
            //m为0时，str1变成str2最少操作数是str1插入字符
            for (int i = 1; i <= n; i++) {
        
                dp[0][i] = dp[0][i - 1] + 1;
            }
            //n为0时，str1变成str2最少操作数是str1删除字符
            for (int i = 1; i <= m; i++) {
        
                dp[i][0] = dp[i - 1][0] + 1;
            }
            for (int i = 1; i <= m; i++) {
        
                for (int j = 1; j <= n; j++) {
        
                    //不需要额外操作
                    if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
        
                        dp[i][j] = dp[i - 1][j - 1];
                    } else {
        
                        //插入、删除、修改都可以
                        dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                    }
                }
            }
            return dp[m][n];
        }
    
        /**
         * BM78 打家劫舍(一)
         */
        public int rob (int[] nums) {
        
            int n = nums.length;
            int[] dp = new int[n + 1];
            dp[1] = nums[0];
            for (int i = 2; i <= n; i++) {
        
                //偷这家，不偷这家
                dp[i] = Math.max(nums[i - 1] + dp[i - 2], dp[i - 1]);
            }
            return dp[n];
        }
    
        /**
         * BM79 打家劫舍(二)
         */
        public int rob2 (int[] nums) {
        
            int n = nums.length;
            int[] dp = new int[n + 1];
            //必须要分情况了
            //偷第一家,最后一家不可以偷
            dp[1] = nums[0];
            for (int i = 2; i < n; i++) {
        
                //偷这家，不偷这家
                dp[i] = Math.max(nums[i - 1] + dp[i - 2], dp[i - 1]);
            }
            int res = dp[n - 1];
            //不偷第一家
            Arrays.fill(dp, 0);
            dp[1] = 0;
            for (int i = 2; i <= n; i++) {
        
                //偷这家，不偷这家
                dp[i] = Math.max(nums[i - 1] + dp[i - 2], dp[i - 1]);
            }
            return Math.max(res, dp[n]);
        }
    
        /**
         * BM80 买卖股票的最好时机(一)
         */
        public int maxProfit (int[] prices) {
        
            int n = prices.length;
            if (n == 0) return 0;
            int res = 0;
            int min = prices[0];
            for (int i = 1; i < n; i++) {
        
                res = Math.max(prices[i] - min, res);
                min = Math.min(min, prices[i]);
            }
            return res;
        }
    
        /**
         * BM81 买卖股票的最好时机(二)
         */
        public int maxProfit1 (int[] prices) {
        
            int n = prices.length;
            if (n <= 1) return 0;
            int res = 0;
            for (int i = 1; i < n; i++) {
        
                if (prices[i] - prices[i - 1] > 0) {
        
                    res += prices[i] - prices[i - 1];
                }
            }
            return res;
        }
    
        /**
         *
         */
    }