读书笔记之《程序员代码面试指南（递归和动态规划）》
BitTigerio 2018-01-29
递归：将问题分解成子问题求解，从较小的问题逐渐逼近原始问题，很多时候只需要在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;
}
}
