动态规划强化

动态规划空间优化   滚动数组

1 House Robber

    public long houseRobber(int[] a) {
        if (a == null || a.length == 0) {
            return 0;
        }
        if (a.length == 1) {
            return a[0];
        }
        if (a.length == 2) {
            return Math.max(a[0], a[1]);
        }
        long[] res = new long[a.length];
        res[0] = a[0];
        res[1] = Math.max(a[0], a[1]);
        for (int i = 2; i < a.length; i++) {
            res[i] = Math.max(res[i - 1], res[i - 2] + a[i]);
        }
        return res[a.length - 1];
     }

    public long houseRobber(int[] a) {
        if (a == null || a.length == 0) {
            return 0;
        }
        if (a.length == 1) {
            return a[0];
        }
        if (a.length == 2) {
            return Math.max(a[0], a[1]);
        }
        long[] res = new long[2];
        res[0] = a[0];
        res[1] = Math.max(a[0], a[1]);
        for (int i = 2; i < a.length; i++) {
            res[i % 2] = Math.max(res[(i - 1) % 2], res[(i - 2) % 2] + a[i]);
        }
        return res[(a.length - 1) % 2];
     }

2 Maximal Square

   public int maxSquare(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int max = 0;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = matrix[i][0];
            max = Math.max(max, dp[i][0]);
            for (int j = 1; j < n; j++) {
                if (i == 0) {
                    dp[i][j] = matrix[i][j];
                } else {
                    if (matrix[i][j] == 1) {
                        dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
                    }
                }
                max = Math.max(max, dp[i][j]);
            }
        }
        return max * max;
    }

    public int maxSquare(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int max = 0;
        int[][] dp = new int[2][n];
        for (int i = 0; i < m; i++) {
            dp[i % 2][0] = matrix[i][0];
            max = Math.max(max, dp[i % 2][0]);
            for (int j = 1; j < n; j++) {
                if (i == 0) {
                    dp[i % 2][j] = matrix[i][j];
                } else {
                    if (matrix[i][j] == 1) {
                        dp[i % 2][j] = Math.min(dp[(i - 1) % 2][j - 1], Math.min(dp[i % 2][j - 1], dp[(i - 1) % 2][j])) + 1;
                    } else {
                        dp[i % 2][j] = 0;
                    }
                }
                max = Math.max(max, dp[i % 2][j]);
            }
        }
        return max * max;

局部最 优 和全局最 优实现时间优

1 Maximum Subarray

    public int maxSubArray(int[] nums) {
        // write your code here
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] local = new int[nums.length];
        int global = nums[0];
        local[0] = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            local[i] = Math.max(local[i - 1] + nums[i], nums[i]);
            global = Math.max(global, local[i]);
        }
        
        return global;
    }

2 Maximum Product Subarray

    public int maxProduct(int[] nums) {
        // write your code here
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        int max_local = nums[0];
        int min_local = nums[0];
        int global = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int max_copy = max_local;
            max_local = Math.max(Math.max(nums[i] * max_local, nums[i]), nums[i] * min_local);
            min_local = Math.min(Math.min(nums[i] * max_copy, nums[i]), nums[i] * min_local);
            global = Math.max(global, max_local);
        }
        return global;
    }

3 Best Time to Buy and Sell Stock

    public int maxProfit(int k, int[] prices) {
        // write your code here
        if (k >= prices.length) {
            int profit = 0;
            for (int i = 1; i < prices.length; i++) {
                if (prices[i] > prices[i - 1]) {
                    profit += prices[i] - prices[i - 1];
                }
            }
            return profit;
        }
        int[] local = new int[k + 1];
        int[] global = new int[k + 1];
        for (int i = 0; i < prices.length - 1; i++) {
            int diff = prices[i + 1] - prices[i];
            for (int j = k; j > 0; j--) {
                local[j] = Math.max(global[j - 1] + Math.max(diff, 0), local[j] + diff);
                global[j] = Math.max(global[j], local[j]);
            }
        }
        return global[k];
    }

 记忆化搜索

本质上：动态规划
动态规划就是解决了重复计算的搜索
动态规划的实现方式：
1. 循环（从小到大递推）
2. 记忆化搜索(从大到小搜索) -> 万金油

什么 时 候用 记忆 化搜索？
1. 状态转移特别麻烦，不是顺序性。
2. 初始化状态不是很容易找到

For I = 1 ->n
dp[i] = search (i)
// 搜索
int search(int i)
{
if(visit[i] == 1)
return dp[i];
if(smallest state)
{
set smallest state
} else {
// to update (i,) , we might need other state
// such as (i-1), (i+1)
for other state
update dp[i] = max(search(i-1) , search(i+1))
}
visit[i] = 1;
return dp[i];
}

1 Longest Increasing continuous Subsequence 2D

class Solution {

    static int n = 0;
    static int m = 0;
    public int longestIncreasingContinuousSubsequenceII(int[][] a) {
        
        if (a == null || a.length == 0) {
            return 0;
        }
        m = a.length;
        n = a[0].length;
        int[][] dp = new int[m][n];
        boolean[][] flag = new boolean[m][n];
        int max = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = search(i, j, a, dp, flag);
                max = Math.max(max, dp[i][j]);
            }
        }
        return max;
    }
    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, 1, -1};
    private int search(int i, int j, int[][] a, int[][] dp, boolean[][] flag) {
        // TODO Auto-generated method stub
        if (flag[i][j]) {
            return dp[i][j];
        }
        int res = 1;
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n) {
                if (a[x][y] > a[i][j]) {
                    res = Math.max(res, search(x, y, a, dp, flag) + 1);
                }
            }
        }
        flag[i][j] = true;
        dp[i][j] = res;
        return res;
    }
}

博弈 类

1 Coins in a line

    public boolean firstWillWin(int n) {
        // write your code here
        int[] dp = new int[n + 1];
        return search(n, dp);
    }
    public boolean search(int n, int[] dp) {
        if (dp[n] != 0) {
            if (dp[n] == 1) {
                return false;
            } else {
                return true;
            }
        }
        if (n <= 0) {
            dp[n] = 1;
        } else if (n == 1) {
            dp[n] = 2;
        } else if (n == 2) {
            dp[n] = 2;
        } else if (n == 3) {
            dp[n] = 1;
        } else {
            if (search(n - 2, dp) && search(n - 3, dp) ||
                search(n - 3, dp) && search(n - 4, dp)) {
                    dp[n] = 2;
                } else {
                    dp[n] = 1;
                }
        }
        return dp[n] == 2;
    }

2 Coins in a line 2

    public boolean firstWillWin(int[] values) {
        // write your code here
        int[] dp = new int[values.length + 1];
        boolean[] flag = new boolean[values.length + 1];
        int sum = 0;
        for (int i : values) {
            sum += i;
        }
        search(values.length, values, dp, flag);
        return dp[values.length] * 2 > sum;
    }
    public int search(int n, int[] values, int[] dp, boolean[] flag) {
        if (flag[n]) {
            return dp[n];
        } 
        flag[n] = true;
        int len = values.length;
        if (n == 0) {
            dp[n] = 0;
        } else if (n == 1) {
            dp[n] = values[len - 1];
        } else if (n == 2) {
            dp[n] = values[len - 1] + values[len - 2]; 
        } else if (n == 3) {
            dp[n] = values[len - 2] + values[len - 3];
        } else {
            dp[n] = Math.max(
                Math.min(search(n - 2, values, dp, flag), search(n - 3, values, dp, flag)) + values[len - n],
                Math.min(search(n - 3, values, dp, flag), search(n - 4, values, dp, flag)) + values[len - n] + values[len - n + 1]
                );
        }
        return dp[n];
    }

3 Coins in a line 2

public boolean firstWillWin(int[] values) {

    int n = values.length;
    int[][] dp = new int[n + 1][n + 1];
    boolean[][] flag = new boolean[n + 1][n + 1];
    
    int sum = 0;
    for (int i : values) {
        sum += i;
    }
    return search(0, n - 1, values, dp, flag) * 2 > sum;
}

private int search(int i, int j, int[] val, int[][] dp, boolean[][] flag) {
    // TODO Auto-generated method stub
    if (flag[i][j]) {
        return dp[i][j];
    }
    flag[i][j] = true;
    if (i > j) {
        dp[i][j] = 0;
    } else if (i == j) {
        dp[i][j] = val[i];
    } else if (i + 1 == j) {
        dp[i][j] = Math.max(val[i], val[j]);
    } else {
        int pick_left = Math.min(dp[i + 2][j], dp[i + 1][j - 1]) + val[i];
        int pick_right = Math.min(dp[i + 1][j - 1], dp[i][j - 2]) + val[j];
        dp[i][j] = Math.max(pick_left, pick_right);
    }
    return dp[i][j];
}

区 间类Dp

1 Stone-Game

有一个石子归并的游戏。最开始的时候，有n堆石子排成一列，目标是要将所有的石子合并成一堆。合并规则如下：

每一次可以合并相邻位置的两堆石子
每次合并的代价为所合并的两堆石子的重量之和
求出最小的合并代价。

您在真实的面试中是否遇到过这个题？ Yes
样例
对于石子序列：[4, 1, 1, 4]（每个数代表这堆石子的重量），最优合并方案下，合并代价为 18：

1. 合并第2堆和第3堆 => [4, 2, 4], 代价 +2
2. 合并前两堆 => [6, 4]，代价 +6
3. 合并剩下的两堆 => [10]，代价 +10
其他例子：
[1, 1, 1, 1] 代价为 8
[4, 4, 5, 9] 代价为 43

    public int stoneGame(int[] a) {
        if (a == null || a.length == 0) {
            return 0;
        }
        int n = a.length;
        int[][] sum = new int[n][n];
        int[][] dp = new int[n][n];
        boolean[][] flag = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            sum[i][i] = a[i];
            for (int j = i + 1; j < n; j++) {
                sum[i][j] = sum[i][j + 1] + a[j];
            }
        }
        return search(0, n - 1, sum, dp, flag);
    }

    private int search(int i, int j, int[][] sum, int[][] dp, boolean[][] flag) {
        // TODO Auto-generated method stub
        if (flag[i][j]) {
            return dp[i][j];
        }
        if (i == j) {
            flag[i][j] = true;
            return dp[i][j];
        }
        flag[i][j] = true;
        for (int k = i; k < j; k++) {
            dp[i][j] = Math.min(dp[i][j], search(i, k, sum, dp, flag) + search(k + 1, j, sum, dp, flag) + sum[i][j]);
        }
        return dp[i][j];
    }

2  312. Burst Balloons

public int maxCoins(int[] nums) {
        int n = nums.length;
        int[] newnum = new int[n + 2];
        newnum[0] = 1;
        for (int i = 0; i < n; i++) {
            newnum[i + 1] = nums[i];
        }
        newnum[n + 1] = 1;
        int[][] dp = new int[n + 2][n + 2];
        return search(newnum, 0, n + 1, dp);
    }
    int search(int[] nums, int l, int r, int[][] dp) {
        if (dp[l][r] != 0) {
            return dp[l][r];
        }
        if (l + 2 == r) {
            dp[l][r] = nums[l] * nums[l + 1] * nums[r];
            return dp[l][r];
        }
        for (int i = l + 1; i < r; i++) {
            dp[l][r] = Math.max(dp[l][r], search(nums, l, i, dp) + search(nums, i, r, dp) + nums[l] * nums[r] * nums[i]);
        }
        return dp[l][r];
    }

 背包问题

1 Backpack

    public int backPack(int n, int[] a) {
        // write your code here
        int m = a.length;
        boolean[][] dp = new boolean[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            dp[i][0] = true;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i - 1][j] || j >= a[i - 1] && dp[i - 1][j - a[i - 1]];
            }
        }
        for (int i = n; i >= 1; i--) {
            if (dp[m][i]) {
                return i;
            }
        }
        return 0;
    }

2 Backpack II

    public int backPackII(int n, int[] a, int[] v) {
        // write your code here
        int m = a.length;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], j >= a[i - 1] ? dp[i - 1][j - a[i - 1]] + v[i - 1]: 0); 
            }
        }
        int max = 0;
        for (int i = n; i >= 1; i--) {
            max = Math.max(dp[m][i], max);
        }
        return max;
    }