动态规划(二)

给定一个正整数n,可以将其分割成多个数字的和，若要让这些数字的乘机最大，求分割的方法，（至少分成两个数）。返回这个最大的乘机。
如：
n=2,则返回1（2=1+1）
n=10,则返回36（10=3+3+4）

暴力解法

回溯遍历将一个数做分割，时间复杂度O(2^n)

1. 此处以分割4为例，如下图：

2. 对应分割n,如下图：

对应的代码如下：

    int breakInteger(int n) {
        if (n == 1) {
            return 1;
        }
        int res = -1;
        for (int i = 1; i < n - 1; i++) {
            // i*(n-i)加入比较的原因
            // 因为函数breakInteger一定要将一个数字分割成两部分，
            // 所以，如果我们只将n分成两部分不想在往下分割了，那就是 i*(n-i)
            res = max(res, i * (n - i), i * breakInteger(n - i));
        }
        return res;
    }

    int max(int a, int b, int c) {
        return Integer.max(a, Integer.max(b, c));
    }

上面分割n的图中，我们可以看到该题也会出现”重叠子问题“的情况，所以可以进一步进行”记忆化搜索“，将算好的结果记录下来，避免重复运算。

    int breakInteger(int n) {
        int[] memo = new int[n + 1];
        Arrays.fill(memo, -1);
        return breakIntegerCore(n, memo);
    }

    int breakIntegerCore(int n, int[] memo) {
        if (n == 1) {
            return 1;
        }
        if (memo[n] != -1) {
            return memo[n];
        }
        int res = -1;
        for (int i = 1; i < n - 1; i++) {
            // i*(n-i)加入比较的原因
            // 因为函数breakInteger一定要将一个数字分割成两部分，
            // 所以，如果我们只将n分成两部分不想在往下分割了，那就是 i*(n-i)
            res = max(res, i * (n - i), i * breakIntegerCore(n - i, memo));
        }
        memo[n] = res;
        return res;
    }

    int max(int a, int b, int c) {
        return Integer.max(a, Integer.max(b, c));
    }

动态规划

自底向上解决

    int integerBreak(int n) {
        // memo[i]用于存储将数字i进行分割（至少分割成两部分）后，最大的乘积
        int[] memo = new int[n + 1];
        Arrays.fill(memo, -1);

        memo[1] = 1;

        for (int i = 2; i <= n; i++) {
            // 计算memo[i]
            for (int j = 1; j < i - 1; j++) {
                // i*(i-j)
                memo[i] = max(memo[i], j * (i - j), j * memo[i - j]);
            }
        }
        return memo[n];
    }

Perfect Squares

给定一个正整数，寻找最少的完全平方数，使他们的和为n
eg:
12=4+4+4
13=4+9

Decode Ways

一个字符串，包含A-Z的字母，每个字符可以和1-26的数字对应，如：A-1，B-2...Z-26。给出一个数字字符串，问，我们有多少种方法可以解析这个数字字符串？
eg：
AB 可以解析成(1,2)或者12，最终返回2

Unique path

有一个机器人，从一个m*n的矩阵的左上角出发，要达到这个矩阵的有下角，机器人每次只能向右或者向下移动，问一共有多少种不同的路径。