动态规划

斐波那契数列

爬楼梯

每次可以上一阶或者两阶，求有多少种上楼梯的方法。

递推公式：f(n)=f(n-1)+f(n-2)

强盗抢劫

抢劫一排住户，但是不能抢邻近的住户，求最大抢劫金额。

nums[i] 住户的财富

递推公式：f(n)=max(f(n-2)+nums[n], f(n-1))

强盗在环形街区抢劫

递推公式和上一题一样，主要考虑，抢和不抢第一间

抢第一间住户，则不能抢n，范围[0,n-1)

不抢第一间，范围[1,n)

信件错排

所有元素的编号与位置号都不相等的情况叫作错排

递推公式：f(n)=(n-1)*f(n-2)+(n-1)*f(n-1)

简单说明：

f(n)表示n个信件错排的情况数

假设有n个信件，对信件n来说，放错的位置有n-1个，假设放在了位置k上（k!=n）

情况1，位置k上信件放在位置n，剩下n-2个信件有f(n-2)种错排，这n-2个信件都不会放在位置n上

情况2，位置k上的信件不放在位置n，则可以将位置n考虑成一个新的第’k’位，包扩k在内的n-1个元素的每一种错排，都等价于只有n-1个元素的错排（只是其中的第k位需要换为第n位）【这么想的话，作为新的第’k’位，信件k肯定是不会放在第’k’位上的！也就完全不会和情况1有重合情况了！】

情况1和情况2有重叠吗？——答案是没有重叠！

母牛生产

每只小母牛生下来算0岁，第1年1岁，第2年2岁，第3年3岁，3岁称为成熟母牛，会生下一只小母牛。

现在，第一年有1只2岁小母牛，第二年生下1只小母牛。问第n年，有多少只成熟母牛？

n=1, res = 0

n=2, res = 1

n=3, res = 1

n=4, res = 1

n=5, res = 2

n=6, res = 3

每一年的成熟母牛数等于前一年的成熟母牛数加上三年前的成熟母牛数（生下来的宝宝数，因为过去三年了，宝宝变成成熟母牛了）。

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

f5 = f4+f2 = 1+1=2

f6 = f5+f3 = 2+1=3

f7=f6+f4=3+1=4

f8=f7+f5=4+2=6

矩阵路径

矩阵的最小路径和

从左上到右下，找最小的路径和。只能向右、或向下移动。

dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]

只能从上边、或者左边的格子来。 可以优化空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int minPathSum(int[][] grid) {
    if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
    int rows = grid.length, cols = grid[0].length;
    int[] dp = new int[cols];

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (j == 0) { // 第一列，只能从上一行来。这里有个小技巧，先判断j，规避掉dp[0-1]
                dp[j] = dp[j]; // 这一行可以不赋值，空着
            } else if (i == 0) { // 第一行，只能从左边来
                dp[j] = dp[j - 1];
            } else {
                dp[j] = Math.min(dp[j - 1], dp[j]);
            }
            dp[j] += grid[i][j];
        }
    }
    return dp[cols - 1];
}

矩阵的总路径数

规则和上一题一样，求唯一路径有多少条。

dp解法：dp[i][j] = dp[i-1][j] + dp[i][j-1] 从左边和上边（同样可以优化空间，同上）

数学解法：移动总次数s = m+n-2，向下次数d=n-1，唯一路径数 = s中选d个的组合，C(s,d)

1
2
3
4
5
6
7
8
9
10
11
public int uniquePaths(int m, int n) {
    if(m<=0 || n<=0){
        return 0;
    }
    int s = m+n-2, d = Math.min(m-1,n-1);
    long res=1; // 会溢出
    for(int i=1;i<=d;i++){
        res = res * (s-d+i)/i; // 这种写法才能整除
    }
    return (int)res;
}

数组区间

等差递增子区间的个数

A = [0, 1, 2, 3, 4]

dp[i] 表示以 A[i] 为结尾的等差递增子区间的个数。
当 A[i] - A[i-1] == A[i-1] - A[i-2]，那么 [A[i-2], A[i-1], A[i]] 构成一个等差递增子区间。而且在以 A[i-1] 为结尾的递增子区间的后面再加上一个 A[i]，一样可以构成新的递增子区间。

1
2
3
4
5
6
7
8
9
dp[2] = 1
    [0, 1, 2]
dp[3] = dp[2] + 1 = 2
		[0, 1, 2, 3], // [0, 1, 2] 之后加一个 3 
		[1, 2, 3] // 新的递增子区间
dp[4] = dp[3] + 1 = 3
		[0, 1, 2, 3, 4], // [0, 1, 2, 3] 之后加一个 4 
		[1, 2, 3, 4], // [1, 2, 3] 之后加一个 4 
		[2, 3, 4] // 新的递增子区间

因为递增子区间不一定以最后一个元素为结尾，可以是任意一个元素结尾，因此需要返回 dp 数组累加的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        if (nums == null || nums.length < 3) {
            return 0;
        }
        int n = nums.length;
        int[] dp = new int[n];
        for (int i = 2; i < n; i++) {
            if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
                dp[i] = dp[i - 1] + 1;
            }
        }
        int total = 0;
        for (int cnt : dp) {
            total += cnt;
        }
        return total;
    }
}

另外一种数学的方式…可惜之前想多了，想岔了…直接判断A[i] - A[i - 1] == A[i - 1] - A[i - 2]就好！..

注意count*(count+1)/2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public int numberOfArithmeticSlices(int[] A) {
        int count = 0;
        int sum = 0;
        for (int i = 2; i < A.length; i++) {
            if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
                count++;
            } else {
                sum += (count + 1) * (count) / 2;
                count = 0;
            }
        }
        return sum += count * (count + 1) / 2;
    }
}

分割整数

分割整数的最大乘积

要么和整数乘，要么和整数的因子乘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int integerBreak(int n) {
    if (n <= 0) {
        return 0;
    }
    int[] dp = new int[n + 1];
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= i - 1; j++) {
            int p1 = j * (i - j);
            int p2 = dp[j] * (i - j);
            dp[i] = Math.max(dp[i], Math.max(p1, p2));
        }
    }
    return dp[n];
}

按平方数来分割整数

组成n的最少平方数个数。

Example 1:

1
2
3
Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

Example 2:

1
2
3
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int numSquares(int n) {
    List<Integer> squares = new ArrayList<>();
    int square = 1, diff = 3;
    while (square <= n) {
        squares.add(square);
        square += diff;
        diff += 2;
    }

    int[] dp = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        dp[i] = i;
        for (int v : squares) {
            if (v > i) {
                break;
            }
            dp[i] = Math.min(dp[i], dp[i - v] + 1); // 用平方数取前一个数最小个数
        }
    }
    return dp[n];
}

分割整数映射字母

A message containing letters from A-Z is being encoded to numbers using the following mapping:

1
2
3
4
'A' -> 1
'B' -> 2
...
'Z' -> 26

Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

1
2
3
Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2:

1
2
3
Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

dp[i]表示i个字符串的解法，d[i+1]新加入的字符，分为两种情况：

  1. 自己可以映射成字母
  2. 和前一个字符组合可以映射成字母
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int numDecodings(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    int n = s.length();
    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = s.charAt(0) == '0' ? 0 : 1;
    for (int i = 2; i <= n; i++) {
        int first = Integer.parseInt(s.substring(i - 1, i));
        int second = Integer.parseInt(s.substring(i - 2, i));
        if (first >= 1 && first <= 9) {
            dp[i] += dp[i - 1];
        }
        if (second >= 10 && second <= 26) {
            dp[i] += dp[i - 2];
        }
    }
    return dp[n];
}

最长递增子序列

最长递增子序列

O(n^2)解法。还有O(nlogn)解法看不懂！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int lengthOfLIS(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int n = nums.length;
    int[] dp = new int[n];
    dp[0] = 1;
    for (int i = 1; i < n; 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);
            }
        }
    }
    int max = 0;
    for (int cnt : dp) {
        if (cnt > max) {
            max = cnt;
        }
    }
    return max;
}

最长公共子序列

最长公共子序列

dp[i][j表示 S1 的前 i 个字符与 S2 的前 j 个字符最长公共子序列的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int longestCommonSubsequence(String s1, String s2) {
    if (s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0) {
        return 0;
    }
    int len1 = s1.length(), len2 = s2.length();
    int[][] dp = new int[len1 + 1][len2 + 1];
    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
    }
    return dp[len1][len2];
}

背包问题

股票问题

只有一次买入卖出的股票

– 据说贪心

记录当前最小买入价格

计算每个元素和当前最小买入价格的差值，取最大的

有一天cooldown、多次买入卖出的股票

状态机啊…不会…pass!