DP-记忆化搜索

DP-记忆化搜索

文章目录

• 整数替换
• 青蛙过河
• • dfs
  • 自顶向下DP
• 矩阵中的最长递增路径
• 猜数字大小 II

有一类题目只适合自顶向下递归(一般都可以记忆化剪枝优化)，不适合自底向上迭代。

整数替换

添加链接描述

注意数据范围是1 <= n <= 2^31 - 1，所以不可能开一个dp数组
然后n+1会溢出，所以用long

import java.util.HashMap;
import java.util.Map;

class Solution {
    Mapmap;
    public int integerReplacement(int n) {
        map=new HashMap<>();
        return (int) dfs(n*1l);
    }

    private long dfs(long n) {
        if (n==1){
            return 0;
        }
        if (map.containsKey(n)){
            return map.get(n);
        }
        long res;
        if (n%2==0){
            res= dfs(n/2);
        }else {
            res= Math.min(dfs(n-1),dfs(n+1));
        }
        res++;
        map.put(n,res);
        return res;
    }
}

青蛙过河

添加链接描述

dfs

无任何优化的代码，超时！

class Solution {    
    public boolean canCross(int[] s) {
       return dfs(s,0,0); //初始情况：青蛙在0下标，之前跳0步过来的。
    }

    private boolean dfs(int[] s, int begin,int step) {
        if(begin==s.length-1){
            return true;
        }

        for (int i=begin+1;i=step-1 && len<=step+1){
                boolean flag = dfs(s, i, len);
                if(flag){
                    return true;
                }
            }
        }
        return false;
    }
}

自顶向下DP

把二维数组将当前下标begin和上一步跳step步过来的step记录下来。

class Solution {
    int[][]memo; //初始0，-1到不了 1可以到达（不能boolean因为需要记录三种状态）
    public boolean canCross(int[] s) {
        //既然题目说了0位置只能跳1步，那就特判，题目搞特殊化，我凭什么不能特判？
        if(s[1]!=1){
            return false;
        }
        int n=s.length;
        memo=new int[n][n];
        return dfs(s,1,1); //0特判了则从1开始跳
    }

    private boolean dfs(int[] s, int begin,int step) {
        if(begin==s.length-1){
            return true;
        }


        if(memo[begin][step]!=0){ //!=0说明之前到过，可以复用
            return memo[begin][step]==1;
        }

        for (int i=begin+1;i=step-1 && len<=step+1){
                boolean flag = dfs(s, i, len);
                if(flag){
                    memo[begin][step]=1;
                    return true;
                }
            }else if(len>step+1){
                break;
            }
        }
        memo[begin][step]=-1;
        return false;
    }
}

矩阵中的最长递增路径

添加链接描述
常规dfs超时

class Solution {
    int[][]memo;
    int[][]dis={{1,0},{-1,0},{0,1},{0,-1}};
    public int longestIncreasingPath(int[][] matrix) {
        int m=matrix.length,n=matrix[0].length;
        memo=new int[m][n];
        int ans=0;
        //所有位置都作为起点，取最大。
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ans=Math.max(ans,dfs(matrix,i,j));
            }
        }
        return ans;
    }

    private int dfs(int[][] matrix, int i, int j) {
        if(memo[i][j]!=0){
            return memo[i][j];
        }
        memo[i][j]=1;//自己
        //求四个方向中的最大
        for (int[] d : dis) {
            int x=d[0]+i;
            int y=d[1]+j;
            if(x>=0 && x=0 && ymatrix[i][j]){
                memo[i][j]=Math.max(memo[i][j],dfs(matrix,x,y)+1);
            }
        }
        return memo[i][j];
    }
}

猜数字大小 II

添加链接描述
比较容易想到的做法为使用「递归」进行求解。

设计递归函数为 int dfs(int l, int r) 传入参数 l 和 r 代表在范围 [l, r]内进行猜数，返回值为在 [l, r] 内猜中数字至少需要多少钱。

我们可决策的部分为「选择猜哪个数 xx」，而不可决策的是「选择某个数 xx 之后（假设没有猜中），真实值会落在哪边」。

因此为求得「最坏情况下最好」的结果，我们应当取所有的 x中的最小值。

最后，为减少重复计算，我们需要在「递归」基础上加入记忆化搜索。

class Solution {
    int[][]memo;
    public int getMoneyAmount(int n) {
        memo=new int[n+1][n+1];
        return dfs(1,n);
    }

    private int  dfs(int left, int right) {
        if (left>=right){
            return 0 ;
        }
        if (memo[left][right]!=0){
            return memo[left][right];
        }
        int ans=Integer.MAX_VALUE;
        for (int i=left;i<=right;i++){
            int res= i+Math.max(dfs(left,i-1),dfs(i+1,right));
            ans=Math.min(ans,res);
        }
        memo[left][right]=ans;
        return ans;
    }
}