备赛蓝桥杯-算法-动态规划

一、简单

1.爬楼梯

题目：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示：

• 1 <= n <= 45

思路：

//上n级台阶，为上n-1级台阶与n-2级台阶的方案数之和
        //理解：上一次台阶有两种方案，一次爬一阶或者一次爬两阶
        //就假设要爬n阶，那么就只需要递归，知道n-1阶的方案数（代表最后一次爬了一阶）
        //知道n-2阶的方案数（代表最后一次爬了两阶）
        //既然总共有两种方案，那就把两个方案数求和再依次递归
        //但是递归要重复计算很多数据，为了节省空间，就把这些数据都存在数组里
        //这就是记忆化递归后的动态规划 

class Solution {
    public int climbStairs(int n) {
        int[] dp=new int[n+1];
        if(n==0 || n==1)
            return 1;
        dp[0]=dp[1]=1;
        for(int i=2;i<n+1;i++)
        {
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
}

2.杨辉三角

题目：

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:

输入: numRows = 1
输出: [[1]]

提示:

• 1 <= numRows <= 30

class Solution {
    public List<List<Integer>> generate(int numRows) {
        //ArrayList嵌套使用，等同于二维数组，只不过长度是自增
        //需要注意的是，二维列表的每一行，是需要自行添加一维列表的
        //也就是说，二维列表只是给了个空壳，要自己往里面存一维列表才行
        List<List<Integer>> l=new ArrayList<>();
        //如果给定行数为0，返回空列表
        if(numRows==0)
            return l;
        if(numRows==1)//这是递归边界
        {//如果给定行数为1，给l添加第一行一维列表[1]
            l.add(new ArrayList<>());
            l.get(0).add(1);
            //二维列表get(0)代表获取第一行一维列表，
            //获取以后才可以使用一维列表的存储或删除功能
            return l;
        }
        l=generate(numRows-1);//递归关系
        ArrayList<Integer> row=new ArrayList<>();
        row.add(1);
        for(int i=1;i<numRows-1;i++)
        {//此一维列表代表每一行元素，行首和行末元素都是1
        //i=0,i=numRows-1都是1，所以for循环内只需要求中间的元素
        //中间元素等于上一行相邻元素之和,l.get(括号里代表（行数-1）)
            row.add(l.get(numRows-1-1).get(i)+l.get(numRows-1-1).get(i-1));
        }
        row.add(1);
        //把这个一维数列添加进二维数列中
        l.add(row);
        return l;
        //返回上一级递归，行数逐渐增加
    }
}

3.杨辉三角 II 

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:

输入: rowIndex = 3
输出: [1,3,3,1]

示例 2:

输入: rowIndex = 0
输出: [1]

示例 3:

输入: rowIndex = 1
输出: [1,1]

提示:

• 0 <= rowIndex <= 33

思路：

杨辉三角，直接考虑递归是最节省时间节省代码的。
创建一个一维列表，代表一行。
递归三步走：
1.判断递归函数目的:拿过来题，先看返回值，哦，是一维列表，那就确定了递归值是“行”列表；题目输入行号（0对应第一行）返回该行列表
2.判断递归边界，也就是rowIndex==0的情况
3.找递归关系，想要求本行的情况，就要求上一行，递归关系这不就来了
上一行=函数（上一行的行号）；

class Solution {
    public List<Integer> getRow(int rowIndex) {
        ArrayList<Integer> row=new ArrayList<>();
        if(rowIndex==0)
        {
            row.add(1);
            return row;
        }
        List<Integer> lastrow=new ArrayList<>();
        lastrow=getRow(rowIndex-1);
        row.add(1);
        for(int i=1;i<rowIndex;i++)
        {
            row.add(lastrow.get(i-1)+lastrow.get(i));
        }
        row.add(1);
        return row;
    }
}

4.买卖股票的最佳时机

 题目：

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

思路：

1.暴力法，两个for循环嵌套，依次比较差值，毫无疑问，数据域太大，超时

2.动态规划：双指针

设置一个指针buy指向成本最小的值;设置一个指针profit指向获利润最大的值

利润=总金额-成本

这里的动态规划，在于双指针的位置是动态变化的，而且始终代表目前为止最符合条件要求的数值，也就是局部最优解，等到全数组都遍历完成，就由局部最优解变为全局最优解。

class Solution {
    public int maxProfit(int[] prices) {
        int buy=Integer.MAX_VALUE;
        int profit=0;
        for(int i=0;i<prices.length;i++)
        {
            buy=Math.min(buy,prices[i]);
            profit=Math.max(profit,prices[i]-buy);
        }
        return profit;
    }
}

5.比特位计数

 题目：

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

示例 1：

输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10

示例 2：

输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

提示：

• 0 <= n <= 105

 思路：

1.暴力法：运用Java自带的Integer.toBinaryString()函数，可逐个将int数值转换为二进制的字符串，然后再用charAt（）依次遍历判断有几个‘1’字符，将数值存入数组即可

class Solution {
    public int[] countBits(int n) {
        int[] b=new int[n+1];
        if(n==0)
        {
            b[0]=0;
            return b;
        }
        Integer a=0;
        for(int i=1;i<n+1;i++)
        {
            String s=a.toBinaryString(i);
            int count=0;
            for(int j=0;j<s.length();j++)
            {
                if(s.charAt(j)=='1')
                    count++;
            }
            b[i]=count;
        }
        return b;
    }
}

 2.感谢Java法:

运用Java自带的Integer.countBits（int）函数可以自动计算括号内int数的二进制1的个数

class Solution {
    public int[] countBits(int n) {
        int[] num=new int[n+1];
        for(int i=0;i<n+1;i++)
        {
            num[i]=Integer.bitCount(i);
        }
        return num;
    }
}

3.动态规划：

这里的动态规划运用的是找规律的方法，

1.奇数总比相邻且小的偶数多末尾的一个1，例如：2->10,3->11 

2.偶数末尾总是0，所以把末尾的0去掉也不会影响1的个数，而去掉末尾的0，就代表原数除了2，例如：8->1000 4->100 2->10 1->1

于是可知，所有的数二进制的含1的个数，都可以由前面的数推导出来

加一个for循环，由小到大遍历即可

class Solution {
    public int[] countBits(int n) {
        int[] num=new int[n+1];
        for(int i=0;i<n+1;i++)
        {
            if(i%2==1)
            {//奇数比小一的偶数多一个1
                num[i]=num[i-1]+1;
            }
            else
            {//偶数等于除以二以后的1的个数，除二等于右移一位
                num[i]=num[i/2];
            }
        }
        return num;
    }
}

 4.升级版动态规划（动态规划+位运算）节省代码：

方法三，要分出奇数和偶数两种情况，而通过位运算则不需要

简单介绍一下位运算：(需要注意，位运算都是以补码进行运算，正数直接+1转补码，负数先转反码，再+1转补码进行运算）

1.>>右移，代表二进制右移一位，十进制除以2，例如：8>>1 -> 1000>>1 -> 100 -> 4

2.<<左移，代表二进制左移一位，十进制乘2，例如：3>>1 ->11 >>1 ->110 ->6

3.&与运算，遍历每一位二进制数，都为1则结果为1，其它结果均为0

4.| 或运算，遍历每一位二进制数，两者有一方为1则结果都为1，只有两方都为0，结果才为0

5.^异或运算，遍历每一位二进制数，相异为1，相同为0

6.~取反运算，遍历每一位二进制数，1变0,0变1

class Solution {
    public int[] countBits(int n) {
        int[] num=new int[n+1];
        for(int i=0;i<n+1;i++)
        {
            num[i]=num[i>>1]+(i&1);
        }
        return num;
    }
}

6.使用最小花费爬楼梯

题目：

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例 1：

输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。

示例 2：

输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。

提示：

• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999

思路：

给定了一个花费数组，现在求最少花费的路径

1.把整体局部化，先看三节台阶以内的花费

走第一节台阶只有一种走法，走第二节台阶时有两种走法， 走第三节台阶时的走法，要看上第三节台阶时迈了几个台阶，a.要是迈了一个台阶，那就是第二节台阶的走法数；b.要是迈了两个台阶，那就是第一节台阶的走法数，这两个走法加在一起等于第三节的走法数。

这样是统计出来所有走法，现在要求所有走法中花费最少的，那就要在每次选择走一节台阶或者走两节台阶中选择花费最少的。

2.找到递归关系

本节台阶的最少花费=（上节台阶的最少花费，上上节台阶的最少花费）中的最小值。

3.具体实现

递归超时的原因是dfs会重复很多数据，每走一步台阶都需要重复计算前面所有的台阶数

因此我们使用记忆化递归的思想，进行动态规划

设定一个数组dp，存储每一个计算的值，既使用递归思想，又不使用递归

1.递归（超时） 

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n=cost.length;
        return dfs(n,cost);
    }
    public int dfs(int i,int[] cost)
    {
        if(i<=1)
            return 0;
        int res1=dfs(i-1,cost)+cost[i-1];
        int res2=dfs(i-2,cost)+cost[i-2];
        return Math.min(res1,res2);
    }
}

 2.动态规划

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        //贪心算法+动态规划
        int n=cost.length;
        int[] dp=new int[n+1];
        dp[0]=dp[1]=0;
        for(int i=2;i<n+1;i++)
        {
            dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[n];
    }
}

7.第 N 个泰波那契数

 题目：

泰波那契序列 Tn 定义如下： 

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

示例 1：

输入：n = 4
输出：4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

示例 2：

输入：n = 25
输出：1389537

提示：

• 0 <= n <= 37
• 答案保证是一个 32 位整数，即 answer <= 2^31 - 1。

思路：

就是比斐波那契多了一个数，思想都一样，直接递归就可以

然后，就超时了

class Solution {
    public int tribonacci(int n) {
        if(n==0 || n==1)
            return n;
        if(n==2)
            return 1;
        return tribonacci(n-1)+tribonacci(n-2)+tribonacci(n-3);
    }
}

超时的原因是：每次计算数，都要重复计算前面的所有数，标准的树型结构

那就用dp数组把每次计算的数都存起来，自底向上，递归思想

class Solution {
    public int tribonacci(int n) {
        int[] dp=new int[n+1];
        dp[0]=0;
        if(n>0)
        {
            dp[1]=1;
            if(n>1)
            dp[2]=1;
        }
        for(int i=3;i<n+1;i++)
        {
            dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
        }
        return dp[n];
    }
}

8. 判断子序列

题目：

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

示例 1：

输入：s = "abc", t = "ahbgdc"
输出：true

示例 2：

输入：s = "axc", t = "ahbgdc"
输出：false

提示：

• 0 <= s.length <= 100
• 0 <= t.length <= 10^4
• 两个字符串都只由小写字符组成。

思路：

作为一个简单题，其实在升级前是真的不难。

双指针法：

定义两个指针，分别指向s和t字符串，遍历t寻找与s相等的字符，若相等，就让s的指针后移。只是需要注意s可以为空，t也可以为空。 

class Solution {
    public boolean isSubsequence(String s, String t) {
        int right=0;
        if(t.length()==0)
        {
            if(s.length()==0)
                return true;
            return false;
        }
        else
        {
            if(s.length()==0)
                return true;
        }
        for(int i=0,j=0;i<t.length();i++)
        {
            if(s.charAt(j)==t.charAt(i))
            {
                j++;
                right++;
                if(right==s.length())
                    return true;
            }
        }
        return false;
    }
}

 进阶：

如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

思路：

超级巨大的数据域，十亿。。不用想，双指针法跑断了也必然超时。

官方提供了动态规划思路，看了我大受震撼

动态规划法：

定义一个judge数组，将t中每个字母在某一特定下标之后第一次出现的序号存储下来。

judge[t.length()+1][26]

二维数组的行表示t的长度，序号；列表示26个字母。

1.为二维数组的末尾一列全部赋m，

初始化所有字母第一次出现的次序均为数组中永远不可能达到的序号，这个数只要符合条件，是谁都行

意义是：若有字母未出现在字符串t中，则方便记录。

2.从字符串t的末尾逆向遍历，记录每个字母出现时的下标，其它未出现的25个字母继续保持上一次出现的序号。这样正向看时，二维数组中的每一行都记录了在某一间断点后第一次出现的下标。

3.遍历s的每一个字母，在二维数组中以0为起点，寻找第一个与之匹配的字母下标，匹配到了，就更新这个下标，下一次以这个下标为起点，再寻找，这时（m）这个数起到了判断的作用，表征二维数组遍历完了也没找到这个字母，就直接false了

4.假如s成功遍历完，那么就true

这个思路为什么好：

二维数组为s的匹配过程提供了数据库，支持s跳跃式搜索，节省了大把时间。

但其实这道题没有进阶版的题目，找到了以后再编写相应的代码吧。

class Solution {
    public boolean isSubsequence(String s, String t) {
        int n=s.length(),m=t.length();
        int[][] judge=new int[m+1][26];
        Arrays.fill(judge[m],m);
        //设定这个数组的意义在于：
        //数组会记录每个字母在某个下标之后第一次出现的位置
        //若是字符串内都没有出现过某个字母，那么这个字母的顺序默认在末尾
        //若是字符串内出现了某个字母，那么这个字母的顺序等于它出现的下标
        for(int i=m-1;i>=0;i--)
        {
            for(int j=0;j<26;j++)
            {
                if(t.charAt(i)==(char)(j+'a'))
                    judge[i][j]=i;
                else 
                    judge[i][j]=judge[i+1][j];
                //这一步很关键，每个字符自然只能匹配一个字母
                //那么未匹配到的另外25个字母的序号就等于此下标后第一次出现的位置
            }
        }
        int add=0;
        //这个add的作用就是定位下标的位置
        //前文提到：judge数组的作用是记录在某一下标后字母第一次出现的位置
        //这个“某一下标”其实就是遍历s得到的字符在judge数组中第一次出现的序号
        //每找到一个字母，就更新这个字母的下标，在此基础上去寻找s中下一个字母第一次出现的序号
        //又是由局部到整体，又是动态规划，不得不说，太牛了
        for(int i=0;i<n;i++)
        {
            if(judge[add][s.charAt(i)-'a']==m)
                return false;
            add=judge[add][s.charAt(i)-'a']+1;
        }
        return true;
}
}