多少种不同

通常枚举的复杂度 $O (2^{n})$
考虑 dp
考虑背包

背包就是用连续的空间, 记忆能填满背包的组合数

多少种不同

每一步有 k 种选择，每种选择导致不同的状态，到达某种状态时可能的操作数

62. 不同路径 mid

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

解法 1: 数学

$C_{(m - 1) + (n - 1)}^{(m - 1)} = \frac{n * . . . * (m - 1 + n - 1)}{1 * . . . * (m - 1)}$

java

class Solution {
    public int uniquePaths(int m, int n) {
        long ans = 1;
        for (int x = n, y = 1; y < m; ++x, ++y) {
            ans = ans * x / y;
        }
        return (int) ans;
    }
}

解法 2: dp

dp[i][j] = cnt

java

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] f = new int[m][n];
        for (int i = 0; i < m; ++i) {
            f[i][0] = 1;
        }
        for (int j = 0; j < n; ++j) {
            f[0][j] = 1;
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                f[i][j] = f[i - 1][j] + f[i][j - 1];
            }
        }
        return f[m - 1][n - 1];
    }
}

70. 爬楼梯 easy

剑指 Offer 10- II. 青蛙跳台阶问题

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

解法 1: 概率

选择有几个 2; 时间复杂度 $O (n^{2})$

java

class Solution {

    public int climbStairs(int n) {
        int sum = 1;
        // i: 2的个数
        for (int i = 1; i <= n / 2; i++) {
            int cnt1 = n - (2 * i);
            sum += cmn(i + cnt1, i);
        }
        return sum;
    }

    private int cmn(int m, int n) {
        long res = 1L;
        n = Math.min(n, (m - n));
        // m-->m-n+1 / n-->1
        for (int x = m, y = 1; y <= n; x--, y++) {
            // 顺序很重要
            res = res * x / y;
        }
        return (int) res;
    }
}

解法 2: DP

$f (n) = f (n - 1) + f (n - 2)$
$f (0) = 0$
$f (1) = 1$
$f (2) = 2$

java

class Solution {
    public int climbStairs(int n) {
        int n1 = 0, n2 = 0, n3 = 1;
        for (int i = 1; i <= n; i++) {
            n1 = n2;
            n2 = n3;
            n3 = n1 + n2;
        }
        return n3;
    }
}

解法 3: 线性代数-矩阵快速幂

利用矩阵乘法, $O (l o g n)$ , 看题解罢

java

public class Solution {
    public int climbStairs(int n) {
        int[][] q = {{1, 1}, {1, 0}};
        int[][] res = pow(q, n);
        return res[0][0];
    }

    public int[][] pow(int[][] a, int n) {
        int[][] ret = {{1, 0}, {0, 1}};
        while (n > 0) {
            if ((n & 1) == 1) {
                ret = multiply(ret, a);
            }
            a = multiply(a, a);
            n >>= 1;
        }
        return ret;
    }

    public int[][] multiply(int[][] a, int[][] b) {
        int[][] c = new int[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
            }
        }
        return c;
    }
}

91. 解码方法 mid

一条包含字母 A-Z 的消息通过以下映射进行了编码：

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

要解码已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：

"AAJF" ，将消息分组为 (1 1 10 6)
"KJF" ，将消息分组为 (11 10 6)

注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。

给你一个只含数字的非空字符串 s，请计算并返回解码方法的总数。

解法 DP

f(n) = f(n-1) + f(n-2)

java

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        if (s.charAt(0) == '0') return 0;
        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) != '0')
                dp[i] = dp[i - 1];

            if (i == 1) dp[i]++; // 2 个元素本身算 1 种
            else if (s.charAt(i - 1) != '0'
                    && (s.charAt(i - 1) - '0') * 10 + s.charAt(i) - '0' <= 26)
                dp[i] += dp[i - 2];
        }
        return dp[n - 1];
    }
}

96. 不同的二叉搜索树 mid

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的二叉搜索树有多少种？返回满足题意的二叉搜索树的种数。

解法 1 DP

根节点 i 从 1==>n, 左右子树数量相乘
dp 存节点数量和树种类的关系

java

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            // 左子树节点数量
            for (int left = 0; left < i; left++) {
                dp[i] += dp[left] * dp[i - left - 1];
            }
        }
        return dp[n];
    }
}

解法 2 数学

卡特兰数

不同组合的数量

377. 组合总和 Ⅳ mid

给你一个由不同整数组成的数组 nums, 和一个目标整数 target. 请你从 nums 中找出并返回总和为 target 的元素组合的个数.

解法背包

用索引表示空间大小

java

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int num : nums) {
                if (num > i) continue;
                dp[i] += dp[i - num];
            }
        }
        return dp[target];
    }
}

494. 目标和 mid

给你一个整数数组 nums 和一个整数 target 。向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个表达式：例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。返回可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。

解法 1 DFS

$O (2^{n})$

java

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        return findTargetSumWays(nums, 0, target);
    }

    public int findTargetSumWays(int[] nums, int start, int target) {
        if (start == nums.length) return target == 0 ? 1 : 0;
        return findTargetSumWays(nums, start + 1, target + nums[start])
             + findTargetSumWays(nums, start + 1, target - nums[start]);
    }
}

解法 2 背包

$(s u m - n e g) - n e g = s u m - 2 \cdot n e g = t a r g e t$
==> $n e g = (s u m - t a r g e t) / 2$

$d p [i] [j] = d p [i - 1] [j] + d p [i - 1] [j - n u m]$
前 i 个数中任意选择, 满足 sum==j 的数量

java

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        int n = nums.length;
        for (int num : nums) {
            sum += num;
        }
        if (target < 0) target = -target;
        int diff = sum - target;
        if (diff < 0 || diff % 2 != 0) return 0;
        int neg = diff / 2;

        int[][] dp = new int[n + 1][neg + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            int num = nums[i - 1];
            for (int j = 0; j <= neg; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= num) dp[i][j] += dp[i - 1][j - num];
            }
        }
        return dp[n][neg];
    }
}

逆序滚动
$d p [j] = d p [j] + d p [j - n u m]$

java

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (target < 0) target = -target;
        int neg = sum - target;
        if (neg < 0 || neg % 2 != 0) return 0;
        neg /= 2;

        int[] dp = new int[neg + 1];
        dp[0] = 1;
        for (int num : nums) {
            for (int j = neg; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }
        return dp[neg];
    }
}

多少种不同 ​