动态规划（DynamicProgramming）-创新互联

斐波那契额数列 1.爬楼梯

// 上楼梯
public class Ti0070 {// dp[i] = dp[i - 1] + dp[i - 2]
    public int climbStairs(int n) {if (n<= 2) return n;
        int[] dp = new int[n + 1];
        dp[1]= 1; dp[2] = 2;
        for (int i = 3; i<= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    public static void main(String[] args) {Assert.check(2 == new Ti0070().climbStairs(2));
        Assert.check(3 == new Ti0070().climbStairs(3));
    }
}

扩展：一次可以爬1,2,3,…m台阶

为普兰等地区用户提供了全套网页设计制作服务，及普兰网站建设行业解决方案。主营业务为成都网站建设、网站设计、普兰网站设计，以传统方式定制建设网站，并提供域名空间备案等一条龙服务，秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求，就会得到认可，从而选择与我们长期合作。这样，我们也可以走得更远！

public class Ti0070_1 {public int climbStairs(int n) {int m = 2; // 1, 2 一次可跳
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i<= n; i++) {for (int j = 1; j<= m; j++) {if (i - j >= 0) dp[i] += dp[i - j];
                else break;
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {Assert.check(2 == new Ti0070().climbStairs(2));
        Assert.check(3 == new Ti0070().climbStairs(3));
    }
}

2.强盗抢劫

public class Ti0198 {public int rob(int[] nums) {int[] dp = new int[nums.length + 1];
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i<= nums.length; i++) {dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        return dp[nums.length];
    }

    public static void main(String[] args) {Assert.check(4 == new Ti0198().rob(new int[]{1, 2, 3, 1}));
        Assert.check(12 == new Ti0198().rob(new int[]{2, 7, 9, 3, 1}));
    }
}

3.强盗在环形街区抢劫

public class Ti0213 {public int rob(int[] nums) {if (nums.length == 1) return nums[0];
        return Math.max(subRob(Arrays.copyOfRange(nums, 0, nums.length - 1)),
                subRob(Arrays.copyOfRange(nums, 1, nums.length)));
    }

    public int subRob(int[] nums) {int[] dp = new int[nums.length + 1];
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i<= nums.length; i++) {dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        return dp[nums.length];
    }

    public static void main(String[] args) {Assert.check(3 == new Ti0213().rob(new int[]{2, 3, 2}));
        Assert.check(4 == new Ti0213().rob(new int[]{1, 2, 3, 1}));
        Assert.check(3 == new Ti0213().rob(new int[]{1, 2, 3}));
    }
}

4.信件错排

题述：有N个信 和 信封，它们被打乱，求错误装信方式的数量。

5.母牛生产

程序员代码面试指南 - P181
题述：农场中成熟的母牛每年都会生 1 头小母牛，且永生。第一年有 1 只小母牛，从第二年开始，母牛开始生小母牛。每只小母牛 3 年之后成熟又可以生小母牛。给定整数 N，求 N 年后牛的数量。

public class GuideP181 {public int getCowCount(int year) {int[] dp = new int[year + 1];
        dp[0] = 1; dp[1] = 1;
        for (int i = 2; i<= year; i++) {dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[year];
    }

    public static void main(String[] args) {Assert.check(21 == new GuideP181().getCowCount(7));
    }
}

矩阵路径 1.矩阵的最小路径和

public class Ti0064 {public int minPathSum(int[][] grid) {int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for (int i = 1; i< m; i++) {dp[i][0] = grid[i][0] + dp[i - 1][0];
        }
        for (int i = 1; i< n; i++) {dp[0][i] = grid[0][i] + dp[0][i - 1];
        }
        for (int i = 1; i< m; i++) {for (int j = 1; j< n; j++) {dp[i][j] = grid[i][j] += Math.min(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[m - 1][n - 1];
    }

    public static void main(String[] args) {Assert.check(7 == new Ti0064().minPathSum(new int[][]{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}));
        Assert.check(12 == new Ti0064().minPathSum(new int[][]{{1, 2, 3}, {4, 5, 6}}));
    }
}

2.矩阵的总路径数

public class Ti0062 {public int uniquePaths(int m, int n) {int[][] dp = new int[m][n];
        Arrays.fill(dp[0], 1);
        for (int i = 1; i< m; i++) {dp[i][0] = 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) {Assert.check(28 == new Ti0062().uniquePaths(3, 7));
        Assert.check(3 == new Ti0062().uniquePaths(3, 2));
        Assert.check(6 == new Ti0062().uniquePaths(3, 3));
    }
}

数组区间 1.数组区间和

public class Ti0303 {public static void main(String[] args) {NumArray numArray = new NumArray(new int[]{-2, 0, 3, -5, 2, -1});
        Assert.check(1 == numArray.sumRange(0, 2));
        Assert.check(-1 == numArray.sumRange(2, 5));
        Assert.check(-3 == numArray.sumRange(0, 5));
    }
}

class NumArray {private int[] sums;

    public NumArray(int[] nums) {sums = new int[nums.length];
        if (nums.length == 0) return;
        sums[0] = nums[0];
        for (int i = 1; i< nums.length; i++) {sums[i] = sums[i - 1] + nums[i];
        }
    }

    public int sumRange(int left, int right) {if (left == 0) return sums[right];
        return sums[right] - sums[left - 1];
    }
}

2.数组中等差递增子区间的个数

public class Ti0413 {public int numberOfArithmeticSlices(int[] nums) {if (nums.length<= 2) return 0;
        int res = 0;
        int[] dp = new int[nums.length];
        for (int i = 2; i< nums.length; i++) {if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {dp[i] = dp[i - 1] + 1;
                res += dp[i];
            }
        }
        return res;
    }

    public static void main(String[] args) {Assert.check(3 == new Ti0413().numberOfArithmeticSlices(new int[]{1, 2, 3, 4}));
    }
}

分割整数 1.分割整数的大乘积

public class Ti0343 {public int integerBreak(int n) {// 存放乘积大值
        int[] dp = new int[n + 1];
        // i-被拆分数
        for (int i = 2; i<= n; i++) {// j-拆分出1,2,...i-1, 但一半就行, 其余都是相反的. 1*3 3*1...
            for (int j = 1; j< i / 2 + 1; j++) {dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {Assert.check(1 == new Ti0343().integerBreak(2));
        Assert.check(36 == new Ti0343().integerBreak(10));
    }
}

2.按平方数来分割整数

public class Ti0279 {public int numSquares(int n) {int[] dp = new int[n + 1];
        for (int i = 1; i<= n; i++) {dp[i] = i;
            for (int j = 1; i - j * j >= 0; j++) {dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {Assert.check(3 == new Ti0279().numSquares(12));
        Assert.check(2 == new Ti0279().numSquares(13));
    }
}

3.分割整数构成字母字符串

public class Ti0091 {public int numDecodings(String s) {int n = s.length();
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int i = 1; i<= n; ++i) {if (s.charAt(i - 1) != '0') {f[i] += f[i - 1];
            }
            if (i >1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0')<= 26)) {f[i] += f[i - 2];
            }
        }
        return f[n];
    }

    public static void main(String[] args) {Assert.check(2 == new Ti0091().numDecodings("12"));
        Assert.check(3 == new Ti0091().numDecodings("226"));
        Assert.check(0 == new Ti0091().numDecodings("06"));
    }
}

最长递增子序列 1.最长递增子序列

public class Ti0300 {public int lengthOfLIS(int[] nums) {int res = 0;
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        for (int i = 0; i< nums.length; i++) {for (int j = 0; j< i; j++) {if (nums[i] >nums[j]) {dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        for (int k : dp) {if (k >res) res = k;
        }
        return res;
    }

    public static void main(String[] args) {Assert.check(4 == new Ti0300().lengthOfLIS(new int[]{10, 9, 2, 5, 3, 7, 101, 18}));
        Assert.check(4 == new Ti0300().lengthOfLIS(new int[]{0, 1, 0, 3, 2, 3}));
        Assert.check(1 == new Ti0300().lengthOfLIS(new int[]{7, 7, 7, 7, 7, 7, 7}));
    }
}

2.一组整数对能构成的最长链

public class Ti0646 {public int findLongestChain(int[][] pairs) {Arrays.sort(pairs, Comparator.comparingInt(o ->o[0]));
        int[] dp = new int[pairs.length];
        Arrays.fill(dp, 1);
        for (int i = 0; i< dp.length; i++) {for (int j = 0; j< i; j++) {if (pairs[j][1]< pairs[i][0]) {dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        int res = 0;
        for (int k : dp) {if (k >res) res = k;
        }
        return dp[pairs.length - 1];
    }

    public static void main(String[] args) {Assert.check(2 == new Ti0646().findLongestChain(new int[][]{{1, 2}, {2, 3}, {3, 4}}));
    }
}

3.最长摆动子序列

public class Ti0376 {public int wiggleMaxLength(int[] nums) {int n = nums.length;
        if (n< 2) {return n;
        }
        int up = 1, down = 1;
        for (int i = 1; i< n; i++) {if (nums[i] >nums[i - 1]) {up = down + 1;
            } else if (nums[i]< nums[i - 1]) {down = up + 1;
            }
        }
        return Math.max(up, down);
    }

    public static void main(String[] args) {Assert.check(6 == new Ti0376().wiggleMaxLength(new int[]{1, 7, 4, 9, 2, 5}));
        Assert.check(7 == new Ti0376().wiggleMaxLength(new int[]{1, 17, 5, 10, 13, 15, 10, 5, 16, 8}));
    }
}

最长公共子序列 1.最长公共子序列

public class Ti1143 {public int longestCommonSubsequence(String text1, String text2) {int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i<= m; i++) {char c1 = text1.charAt(i - 1);
            for (int j = 1; j<= n; j++) {char c2 = text2.charAt(j - 1);
                if (c1 == c2) {dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {Assert.check(3 == new Ti1143().longestCommonSubsequence("abcde", "ace"));
        Assert.check(3 == new Ti1143().longestCommonSubsequence("abc", "abc"));
        Assert.check(0 == new Ti1143().longestCommonSubsequence("abc", "def"));
    }
}

…待续

0-1背包 1.划分数组为和相等的两部分 2.改变一组数的正负号使得它们的和为一给定数 3.01字符串构成最多的字符串 4.找零钱的最少硬币数 5.找零钱的硬币数组合 6.字符串按单词列表分割 7.组合总和 股票交易 1.需要冷却的股票交易 2.需要交易费用的股票交易 3.只能进行两次的股票交易 4.只能进行k次的股票交易 字符串编辑 1.删除两个字符串的字符使它们相等 2.编辑距离 3.复制粘贴字符

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

文章标题：动态规划（DynamicProgramming）-创新互联
转载来源：http://cdkjz.cn/article/coiech.html