读书笔记之《程序员代码面试指南(递归和动态规划)》

递归:将问题分解成子问题求解,从较小的问题逐渐逼近原始问题,很多时候只需要在f(n-1)中加入或移除某些东西或稍作修改就可以求得f(n)

递归 是 考虑所有的情况,一般使用搜索(DFS /BFS)来实现。

一般可以使用记忆化搜索进行优化的递归算法,我们可以使用DP来进行优化。

斐波那契系列问题

经典斐波那契问题

代码就不写了,这个基本都会,需要注意的是:

递归方法的时间复杂度是:$O(2^N)$

顺序计算的时间复杂度是:$O(N)$

二阶递推数列的时间复杂度是:$O(logN)$

大牛小牛问题

假设农场中成熟的母牛每年只会生1头小母牛,并且永远不会死。

第一年农场有1只成熟的母牛,从第二年开始,母牛开始生小母牛。

每只小母牛3年之后成熟又可以生小母牛。

给定整数N,求出N年后牛的数量。

【举例】N=6,第1年1头成熟母牛记为a;

第2年a生了新的小母牛,记为b,总牛数为2;

题目最优解第3年a生了新的小母牛,记为c,总牛数为3;

第4年a生了新的小母牛,记为d,总牛数为4。

第5年b成熟了,a和b分别生了新的小母牛,总牛数为6;

第6年c也成熟了,a、b和c分别生了新的小母牛,总牛数为9,返回9。

【要求】对以上所有的问题,请实现时间复杂度O(logN)的解法。

有 $F(N)=F(N-1)+F(N-3)$

用一个矩阵乘法,且状态矩阵为$3*3$

public int c3(int n){
  if(n<){
    return ;
  }
  if(n==||n==||n=){
    return n;
  }
  int base[][]={{,,},{,,},{,,}};  //构造矩阵
  int [][] res = matrixPower(base,n-3);  //矩阵n-3次方
  return *res[][]+*res[][]+res[][];  
}

矩阵的最小路径和

题目描述

有一个矩阵map,它每个格子有一个权值。从左上角的格子开始每次只能向右或者向下走,最后到达右下角的位置,路径上所有的数字累加起来就是路径和,返回所有的路径中最小的路径和。

给定一个矩阵map及它的行数n和列数m,请返回最小路径和。

EG:

1 、3 、5 、9

8 、1 、3、4

5、0、6、1

8、8、4、0

经典动态规划方法

最终生成的dp矩阵如下:

1、4、9、18

9、5、8、12

14、5、11、12

22、13、15、12

因为第一行和第一列只有一条路走,就是一直沿着走;

第二行,第二列开始就是选择从上往下还是从左往右走;

每次都把每一步的最小路径加起来

时间复杂度$O(MN)$ ,空间复杂度$O(MN)$

public class CircleDynamic {
    public static void main(String [] args){
        int [][] m= {{1,3,5,9},
                    {8,1,3,4},
                    {5,0,6,1},
                    {8,8,4,0}};
        System.out.println(minPathSum1(m));
    }

    public static int minPathSum1(int [] []m){
        if (m == null || m.length == 0 || m[0]==null || m[0].length==0) {
            return 0;
        }
        int row=m.length;
        int col=m[0].length;
        int [][] dp=new int [row][col];
        dp[0][0]=m[0][0];
        for(int i=1;i<row;i++){
            dp[i][0]=dp[i-1][0]+m[i][0];
        }

        for(int j=1;j<col;j++){
            dp[0][j]=dp[0][j-1]+m[0][j];
        }

        for(int i=1;i<row;i++){
            for(int j=1;j<col;j++){
                dp[i][j]=Math.min(dp[i][j-1]+m[i][j],dp[i-1][j]+m[i][j]);
            }
        }
        return dp[row-1][col-1];
    }
}

压缩空间方法

时间复杂度$O(M*N)$ ,空间复杂度$O(min ( M,N ))$

public class CircleDynamic {
    public static void main(String [] args){
        int [][] m= {{1,3,5,9},
                    {8,1,3,4},
                    {5,0,6,1},
                    {8,8,4,0}};
        System.out.println(minPathSum1(m));
    }

    public static int minPathSum1(int [] []m){
        if (m == null || m.length == 0 || m[0]==null || m[0].length==0) {
            return 0;
        }
        int more = Math.max(m.length,m[0].length);
        int less= Math.min(m.length,m[0].length);
        boolean rowmore=more==m.length;
        int arr[] = new int [less];
        arr[0]=m[0][0];
        for(int i=1;i<less;i++){
            arr[i]=arr[i-1]+(rowmore?m[0][i]:m[i][0]);
        }
        for(int i=1;i<more;i++){
            arr[0]=arr[0]+(rowmore?m[i][0]:m[0][i]);
            for(int j=1;j<less;j++){
                arr[j]=Math.min(arr[j],arr[j-1])+(rowmore?m[i][j]:m[j][i]);
            }
        }
      return arr[less-1];
    }
}

换钱的最少货币数

题目:

给定数组arr, arr中所有的值都为正数且不重复。每个值代表一中面值的货币,每种面值的货币可以使用任意张,再给定一个整数aim代表要找的钱数,求组成aim的最少货币数。

思路:

如果arr的长度为N, 则生成一个行数为N, 列数为aim+1的动态规划表dp[N][aim+1], dp[i][j]的含义为:在可以任意使用arr[0...i]货币的情况下,组成j所需的最小张数。

设: arr=[5,2,3,1] aim = 5

1.dp[0..N-1][0]的值表示找钱数为0时需要的最少张数,所以全设为0。(矩阵的第一列)

0 0 0 0 0 0

dp=0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 0

​ 2.dp[0][0...aim]的值表示只能使用arr[0]货币也就是5的情况下,找0 ,1,2,3,4,5的钱的情况下。其中无法找开的一律设为32位的最大值,记为max.

0 max max max max 1

dp= 0

3.剩下的位置依次从左到右,再从上到下计算。假设计算到(i,j)位置,dp[i][j]的值可能来自下面的情况:

完全不使用当前货币arr[i]情况系的最少张数,即dp[i-1][j]的值

只使用一张当前货币arr[i]的情况下的最少张数,即dp[i-1][j-arr[i]]+1 其中 j-arr[i]的值为使用了一张arr[i]后,还需要找多少钱。 i-1是指使用arr[i]之前的钱来兑换

只使用两张当前货币arr[i]的情况下的最少张数,即dp[i-1][j-2*arr[i]]+2

只使用三张当前货币arr[i]的情况下的最少张数,即dp[i-1][j-3*arr[i]]+3

所有情况中,取最小的纸张数。所以:

dp[i][j] = min{dp[i-1][j], dp[i-1][j-k*arr[i]]} + k ==>

dp[i][j] = min{dp[i-1][j], min{dp[i-1][j-x*arr[i]]+x (x >= 1)}} ==>

设x-1 = y >= 0 ==> x = y +1代入得

dp[i][j] = min{dp[i-1][j], min{dp[i-1][j-arr[i]-y*arr[i]+y+1 (y>=0)}}

又因为min{dp[i-1][j-arr[i]-y*arr[i]+ y (y>=0)] =>

dp[i][j-arr[i]] 因为其中 dp[i-1][j-y*arr[i]+y] = dp[i][j]

最终有:dp[i][j] = min{dp[i-1][j], dp[i][j-arr[i]+1]} 如果 j-arr[i] < 0,即发生越界。

说明arr[i]太大了,用一张都会超出钱数j,所以令dp[i][j]=dp[i-1][j]即可。

0 max max max max 1

dp = 0 max 1 max2 1

0max1 1 2 1

01 1 1 2 1

public class CircleDynamic {
    public static void main(String [] args){
        int [] m= {5,2,5,3};
        int aim = 15;
        System.out.println(minCoins(m,aim));
    }

    public static int minCoins(int [] arr,int  aim){
        if(arr==null || arr.length==0|| aim<0){
            return -1;
        }

        int n=arr.length;
        int max=Integer.MAX_VALUE;
        int [][] dp=new int [n][aim+1];
        for(int j=1;j<aim;j++){
            dp[0][j]=max;
            if(j-arr[0]>=0 && dp[0][j-arr[0]]!=max){
                dp[0][j]=dp[0][j-arr[0]]+1;
            }
        }

        int left = 0;
        for(int i=1;i<n ;i++){
            for(int j=1;j<aim;j++){
                left=max;
                if(j-arr[i]>=0&&dp[i][j-arr[i]]!=max){
                    left=dp[i][j-arr[i]]+1;

                }

                dp[i][j]=Math.min(left,dp[i-1][j]);
            }
        }

        for(int i=0;i<n ;i++){
            for(int j=0;j<aim;j++){
                System.out.print(dp[i][j]+ "  " );
                if(j==aim-1){
                System.out.println(" ");
                }
            }
            }
        return dp[n-1][aim] !=max ?dp[n-1][aim-1]:-1;
    }
}

Result:

0  2147483647  2147483647  2147483647  2147483647  1  2147483647  2147483647  2147483647  2147483647  2  2147483647  2147483647  2147483647  2147483647   
0  2147483647  1  2147483647  2  1  3  2  4  3  2  4  3  5  4   
0  2147483647  1  2147483647  2  1  3  2  4  3  2  4  3  5  4   
0  2147483647  1  1  2  1  2  2  2  3  2  3  3  3  4   
4

数组中最长的连续数字序列

给定一个无序的整数序列, 找最长的连续数字序列。

例如:

给定[100, 4, 200, 1, 3, 2],

最长的连续数字序列是[1, 2, 3, 4]。

输出4.

public class Main {
    public static void main(String[] args) {
       int[] arr = {100,4,200,1,3,2};
       System.out.println(longestConsecutive(arr));
    }

    public static int longestConsecutive(int [] arr){
        if(arr.length==0||arr==null){
            return 0;
        }

        int max=1;
        HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
        for(int i=0;i<arr.length;i++){
            if(!map.containsKey(arr[i])){
                map.put(arr[i],1);
                if(map.containsKey(arr[i]-1)){
                    max=Math.max(max,merge(map,arr[i]-1,arr[i]));
                }
                if(map.containsKey(arr[i]+1)){
                    max=Math.max(max,merge(map,arr[i],arr[i]+1));
                }
            }
        }
        return max;
    }

    public static int  merge(HashMap<Integer,Integer> map,int less,int more){
        //计算左边有几个数
        int left=less-map.get(less)+1;
        //计算右边有几个数
        int right=more+map.get(more)-1;
        //合计
        int len=right-left+1;
        //标记
        map.put(left,len);
        map.put(right,len);
        return len;
    }
 }

龙于地下城游戏问题

给定一个二维数组map,含义是一张地图,例如:

{{-2,-3,3},
 {-5,-10,1},
 {0,30,-5}}

游戏规则如下:

骑士从左上角出发,每次只能向下或者向右,直到右下才能见到公主;

每个格子代表骑士遭遇的事件,如果是负数,代表消耗血量,如果是正数,代表血瓶;

骑士走到任何一个位置,血量都不能低于1。

为了让骑士见到公主,骑士初始血量最少为多少?

只能往下或往右,需要一个辅助数组dp[][] 来计算。那么可以逆着来计算。

public class Main {
    public static void main(String[] args) {
       int[][] arr = { {-2,-3,3},
                     {-5,-10,1},
                     {0,30,-5} };
       System.out.println(minHP(arr));
    }

    public static int minHP(int [] [] arr){
        if(arr.length==0||arr==null){
            return 1;
        }

        int row=arr.length;
        int col=arr[0].length;
        int[][] dp=new int [row--][col--];
        dp[row][col]=arr[row][col]>0?1:1-arr[row][col];
        for(int j=col-1;j>=0;j--){
            dp[row][j]=Math.max(dp[row][j+1]-arr[row][j],1);  //计算初步差异值
        }

        int right=0;
        int down=0;
        for(int i=row-1;i>=0;i--){
            dp[i][col]=Math.max(dp[i+1][col]-arr[i][col],1);  //计算初步上下差异值
            for(int j=col-1;j>=0;j--){
                right=Math.max(dp[i][j+1]-arr[i][j],1);  //向右走
                down=Math.max(dp[i+1][j]-arr[i][j],1);  //向下走
                dp[i][j]=Math.min(right,down);  //取最小的差异值
            }
        }
        return dp[0][0];
    }
 }

最长公共子串问题

所谓最长公共子串,比如

串 str1="1AB2345CD"

串 str2="12345EF";

则它们的最长公共子串为串 "2345",输出4

public class Main {
    public static void main(String[] args) {
        String str1="1AB2345CD";
        String str2="12345EF";
       System.out.println(getdp(str1,str2));
    }

    public static int getdp(String str1,String str2){
        int dp[][]=new int [str1.length()][str2.length()];
        for(int i=0;i<str1.length();i++){
            if(str1.charAt(i)==str2.charAt(0)){
                dp[i][0]=1;
            }
        }

        for(int j=1;j<str2.length();j++){
            if(str1.charAt(0)==str2.charAt(j)){
                dp[0][j]=1;
            }
        }

        int max=0;
        for(int i=1;i<str1.length();i++){
            for(int j=1;j<str2.length();j++){
                if(str1.charAt(i)==str2.charAt(j)){
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                System.out.print(dp[i][j]+" ");
                max=Math.max(max,dp[i][j]);
            }
            System.out.println("");
        }
        return max;
    }
 }

---
0 0 0 0 0 0 
0 0 0 0 0 0 
1 0 0 0 0 0 
0 2 0 0 0 0 
0 0 3 0 0 0 
0 0 0 4 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
4

跳跃游戏

package RecursiveAndDynamic;

/**
 * Created by zdmein on 2017/9/14.
 * 跳跃游戏
 给出一个非负整数数组,你最初定位在数组的第一个位置。
 数组中的每个元素代表你在那个位置可以跳跃的最大长度。   

 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
 给出数组A = [2,3,1,1,4],最少到达数组最后一个位置的跳跃次数是2
 (从数组下标0跳一步到数组下标1,然后跳3步到数组的最后一个位置,一共跳跃2次)

 思路:贪心算法;
 * 从第一个数开始, 寻找可以一个可以跳最远的点;
 * 例1:3 1 2 4 1 0 0
 * 1.从第一个位置0,可以跳到位置1和位置2和位置3;
 * 2.如果跳到位置1,那么最远就可以跳到位置(1+1);
 * 3.如果跳到位置2,那么最远就可以跳到位置(2+2);
 * 4.如果跳到位置3,那么最远就可以跳到位置(3+4);
 * 5.故选择跳到位置3 ,重复1.2.3步;
 *
 * 算法分析:
 * 1.如果选择跳到位置3 ,就无法跳到位置2和位置3, 那么会不会因此错过最优解? 答:不会!
 * 2.因为任意位置1和位置2能到达的位置, 位置3都可以到达;
 * 3.故不会错过最优解;
 */
public class jump1 {
    public static void main(String [] args){
        int [] arr={,,,,,};
        System.out.println(jump(arr));
    }

    public static int jump(int [] arr){
        if(arr==null||arr.length==){
            return ;
        }
        int jump=;
        int cur=;
        int next=;
        for (int i=;i<arr.length;i++){
            if(cur<i){
                jump++;
                cur=next;
            }
            next=Math.max(next,i+arr[i]);
        }
        return jump;
    }
}

读书笔记之《程序员代码面试指南(递归和动态规划)》

相关推荐