暴力递归到动态规划

dp数组的维数–>看可变参数的个数

模型:从左往右尝试模型,范围尝试模型,样本对应模型,业务限制模型

题目一 robotwalk

题目描述:

假设有排成一行的N个位置，记为1～N，N一定大于或等于2开始时机器人在其中的M位置上（M一定是1～N中的一个）如果机器人来到1位置，那么下一步只能往右来到2位置；

如果机器人来到N位置，那么下一步只能往左来到N—1位置；如果机器人来到中间位置，那么下一步可以往左走或者往右走；

规定机器人必须走K步，最终能来到P位置（P也是1～N中的一个）的方法有多少种给定四个参数N、M、K、P，返回方法数。

方法一(纯递归dfs)(有大量的重复计算):

//方法一:纯暴力搜索(dfs，递归)
//机器人当前来到的位置是cur
//机器人还有rest步需要去走
//最终的目标是aim
//有哪些位置？1-N
//返回：机器人从cur出发，走过rest步之后，最终停在aim的方法数是多少
int process1(int cur,int rest,int aim,int N){
    if(rest==0){//如果已经不需要走了，走完了
        return  cur==aim?1:0;
    }
    //rest>0，还有步数要走
    if(cur==1){ //1->2
    return process1(2,rest-1,aim,N);
    }
    if(cur==N){//N-1<-N
    return process1(N-1,rest-1,aim,N);
    }
    //中间位置上!
    return process1(cur-1,rest-1,aim,N)+process1(cur+1,rest-1,aim,N);//第一步往左走的方法数加上第一步往右走的方法数
    
}

方法二(记忆化搜索)(避免重复计算)：

//方法二:
//cur范围：1~N
//rest范围:0~rest  两者确定dp二维数组的大小确保任意数据均能装在该二维数组中
int process2(int cur,int rest,int aim,int N,int dp[][]){
    // dp[cur][rest]==-1  --> process2(cur,rest)之前没算过
    // dp[cur][rest]!=-1  --> process2(cur,rest)之前算过 返回值,dp[cur][rest]    
    dp[N+1][rest+1];
    for(int i=0;i<=N;i++){
        for(int j=0;j<=rest;j++){
            dp[i][j]=-1;
        }
    }						//这块二维数组的赋值处理可能会出现编译错误
    if(dp[cur][rest]!=-1){
        return dp[cur][rest];
    }
    //之前没算过
    int ans=0;
    if(rest==0){
        ans=cur==aim?1:0;
    }
    else if(cur==1) ans=process2(2,rest-1,aim,N,dp);
    else if(cur==N) ans=process2(N-1,rest-1,aim,N,dp);
    else    ans=process2(cur-1,rest-1,aim,N,dp)+process2(cur+1,rest-1,aim,N,dp);
    dp[cur][rest]=ans;//记录当前的数据
    return ans;
}

方法三(动态规划):

int process3(int N<int start,int aim,int K){//K相当于上面的rest,指的是要走的总步数
    int dp[][]=new int[N+1][K+1];//初始的数组默认值为0
    dp[aim][0]=1;// dp[...][0]=0;
    for(int rest=1;rest<=K;rest++){ //列
    dp[1][rest]=dp[2][rest-1];
        for(int cur=2;cur<N;cur++){
            dp[cur][rest]=dp[cur-1][rest-1]+dp[cur+1][rest-1];
        }
        dp[N][rest]=dp[N-1][rest-1];
    }
    return dp[start][K];
    
}

题目二 CardsinLine

题目描述:

给定一个整型数组arr，代表数值不同的纸牌排成一条线

玩家A和玩家B依次拿走每张纸牌

规定玩家A先拿，玩家B后拿

但是每个玩家每次只能拿走最左或最右的

纸牌玩家A和玩家B都绝顶聪明

请返回最后获胜者的分数。

方法一(递归):

//根据规则，返回获胜者的分数
int win1(int arr[]){
    if(arr==NULL||arr.length==0) return 0; 
    int first=f1(arr,0,arr.length-1);
    int second=g1(arr,0,arr.length-1);
    return max(first,second);
}

//arr[L...R],先手获得的最好分数返回
int f1(int arr[],int L,int R){
    if(L==R) return arr[L];
    int p1=arr[L]+g1(arr,L+1,R);
    int p2=arr[R]+g1(arr,L,R-1);
    return max(p1,p2);
}

//arr[L...R],后手获得的最好分数返回
int g1(int arr[],int L,int R){
    if(L==R) return 0;
    int p1=f1(arr,L-1,R);//对手拿走了L位置的数
    int p2=f1(arr,L,R-1);//对手拿走了R位置的数
    return min(p1,p2);
}

方法二(记忆化搜索):

//根据规则，返回获胜者的分数
int win2(int arr[]){
    if(arr==NULL||arr.length==0) return 0; 
    int N=arr.length;
    int fmap[N][N];
    int gmap[N][N];
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            fmap[i][j]=-1;
            gmap[i][j]=-1;
        }
    }
    int first=f2(arr,0,arr.length-1,fmap,gmap);
    int second=g2(arr,0,arr.length-1,fmap,gmap);
    return max(first,second);
}

//arr[L...R],先手获得的最好分数返回
int f2(int arr[],int L,int R,int fmap[][],int gmap[][]){
    if(fmap[L][R]!=-1){
        return fmap[L][R];
    }
    int ans=0;
    if(L==R) ans=arr[L];
    else{
    int p1=arr[L]+g2(arr,L+1,R,fmap,gmap);
    int p2=arr[R]+g2(arr,L,R-1,fmap,gmap);
    ans=max(p1,p2);    
    }
    fmap[L][R]=ans;
    return ans;
}

//arr[L...R],后手获得的最好分数返回
int g1(int arr[],int L,int R,int fmap[][],int gmap[][]){
    if(gmap[L][R]!=-1){
        return gmap[L][R];
    }
    int ans=0;
    if(L!=R){
    int p1=f2(arr,L-1,R,fmap,gmap);//对手拿走了L位置的数
    int p2=f2(arr,L,R-1,fmap,gmap);//对手拿走了R位置的数
    ans=min(p1,p2);
    }
    return ans;
}

方法三(动态规划):

题目三 背包问题

题目描述:

01背包问题可描述为如下问题：
有一个容量为bag的背包，还有n个物体。现在忽略物体实际几何形状，我们认为只要背包的剩余容量大于等于物体体积，那就可以装进背包里。每个物体都有两个属性，即体积w和价值v。(v数组与w数组)
问：如何向背包装物体才能使背包中物体的总价值最大？

方法一(递归):

方法二(动态规划):

题目四 数字转字符串

题目描述:
规定1和A对应,2和B对应…26和Z对应

那么一个数字字符串比如”111”就可以转化为:

“AAA”,”KA”,”KA”

给定一个只有数字字符组成的字符串str,返回有多少种转化结果

方法一(递归):

方法二(动态规划):

题目五 贴纸问题

题目描述:

给定一个字符串str，给定一个字符串类型的数组arr，出现的字符都是小写英文arr每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来返回需要至少多少张贴纸可以完成这个任务。

例子：str＝ ＂babac＂， arr ＝ ｛＂ba＂，＂c＂，＂abcd＂｝

至少需要两张贴纸＂ba”和＂abcd”，因为使用这两张贴纸，把每一个字符单独剪开，含有2个a、2个b、1个c。是可以拼出str的。所以返回2。

方法一(递归):

题目六 最长公共子序列

题目描述:

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

• 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

示例 2：

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。

方法一(递归):

方法二(动态规划):

题目七 最长回文子序列

题目描述：

给定一个字符串str,返回这个字符串的最长回文子序列长度

比如:str=”a12b3c43def2ghi1kpm”

最长回文子序列是”1234321”或者”123c321”,返回长度7

方法一(递归):

方法二(动态规划):

题目八 马走日步数

题目描述:

请同学们自行搜索或者想象一个象棋的棋盘

然后把整个棋盘放入第一象限,棋盘的最左下角是(0,0)位置

那么整个棋盘就是横坐标上9条线,纵坐标上10条线的区域

给你三个参数x,y,k

返回”马”从(0,0)位置出发,必须走k步

最后落在(x,y)上的方法数有多少种?

方法一(递归):

方法二(动态规划)(因为可变参数有x,y,rest三个,故dp数组要求是三维的):

题目九 咖啡问题

题目描述:

给定一个数组arr，arr[i]代表第i号咖啡机泡一杯咖啡的时间

给定一个正数N，表示N个人等着咖啡机泡咖啡，每台咖啡机只能轮流泡咖啡只有一台咖啡机，一次只能洗一个杯子，时间耗费a，洗完才能洗下一杯

每个咖啡杯也可以自己挥发干净，时间耗费b，咖啡杯可以并行挥发假设所有人拿到咖啡之后立刻喝干净，

返回从开始等到所有咖啡机变干净的最短时间

三个参数： int[] arr、 int N， int a、 int b

方法一(递归):

题目十 货币数组问题

题目描述：
arr是货币数组，其中的值都是正数.再给定一个正数aim.

每个值都认为是一张货币

即使是值相同的货币也认为每一张都是不同的

返回组成aim的方法数

例如:arr={1,1,1},aim=2

第0个和第1个能组成2,第1个和第2个能组成2,第0个和第2个能组成2

一共就3种方法,所以返回3

方法一(递归):

方法二(动态规划):

题目十一 面值数组问题(与第十题相区别)

题目十和题目十一都是从左往右模型

题目描述:

arr是面值数组,其中的值都是正数且没有重复.再给定一个正数aim

每个值都认为是一种面值,且认为张数是无限的

返回组成aim的方法数

例如: arr={1,2},aim=4

方法如下:1+1+1+1,1+1+2,2+2

一共就3种方法,所以返回3

方法一(递归):

方法二(动态规划):

与之前题目不同的是 之前题目求一个格子的时间复杂度都是O(1)(这时候记忆化搜索与严格表结构的方法同样好),这题求一个格子要用个for循环,即为O(n)(此时可以优化)

通过观察后可以对方法二进一步优化

题目十二 生存概率

题目描述：

给定5个参数，N，M，row，col，k

表示在N*M的区域上,醉汉Bob初始在(row,col)位置

Bob一共要迈出k步,且每步都会等概率向山下左右四个方向走一个单位

任何时候Bob只要离开N*M区域,就直接死亡

返回k步之后,Bob还在N*M的区域的概率

方法一(递归):

方法二(动态规划)(与马走日步数一样):

题目十三 打怪兽问题

题目描述:

给定3个参数,N,M,K

怪兽有N滴雪,等着英雄来砍自己

英雄每一次打击,都会让怪兽流失[0~M]的血量

到底流失多少?每一次在[0~M]上等概率的获得一个值

求K次打击之后,英雄把怪兽砍死的概率

方法一(递归):

方法二(动态规划):

题目十四 面值数组问题Ⅱ

题目描述:

arr是面值数组,其中的值都是正数且没有重复.再给定一个正数aim

每个值都认为是一种面值,且认为张数是无限的.

返回组成aim的最小货币数

方法一(递归):

方法二(动态规划):