DP入门 || 未完待续

今天学一下逃避了一年的dp= = 以下内容整理自九章算法—dp入门

动态规划的类型

• 计数 + *
  计数路径（遍历路径就显然DFS了）
  有多少种方法选出K个数使得和为sum
• 求最大最小值 max min
  最长上升子序列长度
  从左上到右下路径的最大数字和
• 存在性 OR AND
  取石子游戏，先手是否必胜
  能否选出K个数使得和为sum

动态规划的组成部分

⚠️数组大小、计算顺序、初始化、转移

• 确定状态
  dp需要开一个数组，先确定数组的每个元素f[i] or f[i][j]代表什么。
  • 最后一步 的 最优状态，上一步也要最优……
  • 子问题（问题一样，规模变小）
    区别于递归：递归做了太多重复计算，dp记忆化了。
• 确定状态转移方程
• 初始条件、边界情况
  • 转移方程推不出的就是初始，要单独定义，如f(0) = 0, f(-) = ∞。
  • 边界：不要数组越界（下标不为负，且不能超）
• 计算顺序
  跟递归不同，递归的入口是“大”问题，一直压栈再计算出栈返回，“小”问题重复多次进出栈计算了。
  dp是从“小”问题开始，当之后“大”问题用到小问题的结果时，小问题的结果已经算过保存下来了，不用重复计算了。
  例题LintCode669 Coin Change

    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        dp[0] = 0;
        int ntype = coins.length;
        for(int i = 1; i <= amount; i++) {
            dp[i] = Integer.MAX_VALUE;
            for(int j = 0; j < ntype; j++) {
                if(i>= coins[j] && dp[i - coins[j]]!= Integer.MAX_VALUE)
                dp[i] = Math.min(dp[i-coins[j]]+1, dp[i]);
            }
        }
        if(dp[amount] == Integer.MAX_VALUE)
            dp[amount] = -1;
        return dp[amount];
    }

LintCode114 Unique Paths

    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        dp[0][0] = 1;
        for(int i = 0; i < n; i++) 
            dp[0][i] = 1;
        for(int i = 0; i < m; i++)
            dp[i][0] = 1;
        // init其实可以放在for循环里
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                dp[i][j] = dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }

LintCode116 Jump Game

• 动态规划 时间O(n^2) 空间O(n)

    public boolean canJump(int[] A) {
        int nn = A.length;
        boolean[] dp = new boolean[nn];
        dp[0] = true;
        for(int i = 0; i < nn; i++) {
            for(int j = 0; j < i; j++) {
                if(dp[j] && j + A[j] >= i) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[nn-1];
    }

• 贪心 时间O(n) 空间O(n)

LeetCode152 乘积最大子序列

dp题目类型

• 坐标型dp
• 序列型dp
• 划分序列满足某性质
• 区间型dp
• 背包型dp
• 最长序列型dp
• 博弈型dp
• 综合型dp

时间、空间的优化
滚动数组
降维
打印路径