DP EASY 21.11.10

• 121.买卖股票的最佳时机
• • Java实现
• 338.比特位计数
• • Java实现
• 1025.除数博弈
• 1646.获取生成数组中的最大值
• • Java实现

1. 边界：不买不卖，收益为零。
2. 最优子结构：如果当前是最小值，那么最小值一定是买入的时机
3. 状态转移函数：如果当前的股票面额更大，就更新，maxprofit = max(maxprofit, prices[i] - minprice)

class Solution {
    public int maxProfit(int[] prices) {
        int maxprofit = 0, minprice = 10000;
        for (int i:prices){
            minprice = Math.min(minprice, i);
            maxprofit = Math.max(maxprofit, i - minprice);
        }
        return maxprofit;
    }
}

执行用时：2 ms, 在所有 Java 提交中击败了92.98%的用户
内存消耗：50.9 MB, 在所有 Java 提交中击败了93.91%的用户

1. 边界： 0是0，1是1

2. 最优子结构

3. 状态转移方程：每当增加一个2的倍数，二进制位就多1。

偶数的二进制表示个位数一定是0，将偶数除以2等价于将二进制表示右移一位，1的个数不会变。奇数右移一位则会丢掉一个1，因此需要加回来一个1。

class Solution {
    public int[] countBits(int n) {
        if (n == 0){
            int[] lis = {0};
            return lis;
        }
        int[] lis = new int[n + 1];
        lis[0] = 0;
        lis[1] = 1;
        for (int i = 2; i <= n; i++){
            int quo = i / 2;
            int rem = i % 2;
            lis[i] = lis[quo] + rem;
        }
        return lis;
    }
}

执行用时：1 ms, 在所有 Java 提交中击败了99.88%的用户
内存消耗：42 MB, 在所有 Java 提交中击败了94.54%的用户

1. 数学归纳法

class Solution {
    public boolean divisorGame(int n) {
        return n % 2 == 0;
    }
}

2. 动态规划

class Solution {
    public boolean divisorGame(int n) {
        if (n == 1){
            return false;
        }
        boolean[] boo = new boolean[n + 2];
        boo[2] = true;
        for (int i = 3; i <= n; i++){
            for (int j = 1; j < i; j++){
                if (i % j == 0 && !boo[i - j]){
                    boo[i] = true;
                    break;
                }
            }
        }
        return boo[n];
    }
}

执行用时：3 ms, 在所有 Java 提交中击败了25.21%的用户
内存消耗：35.2 MB, 在所有 Java 提交中击败了42.63%的用户

根据奇偶性，可以直接生成。注意特殊值。

class Solution {
    public int getMaximumGenerated(int n) {
        if (n == 0){
            return 0;
        }
        int[] nums = new int[n + 1];
        nums[0] = 0;
        nums[1] = 1;
        int max = 1;
        for (int i = 2; i <= n; i++){
            nums[i] = nums[i / 2] + i % 2 * nums[i / 2 + 1];
            max = Math.max(max, nums[i]);
        }
        return max;
    }
}

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：35.2 MB, 在所有 Java 提交中击败了47.03%的用户