动态规划题目

BM62 斐波那契数列

public class Solution {
    /*
    //方法一：递归	时间复杂度O(n), 没有重复的计算(重复计算2^n)空间复杂度O（n）和递归栈的空间
    int[] tmp = new int[41];
    public int Fibonacci(int n) {
        if(n == 1 || n== 2)
            return 1;
        if(tmp[n] != 0) return tmp[n];
        return tmp[n] = Fibonacci(n - 1) + Fibonacci(n-2);
    }
    */
    /*
    //方法二：动态规划  时间复杂度：O（n）， 空间复杂度：O（n）
    int[] dp = new int[41];
    public int Fibonacci(int n) {
        dp[1] = 1;
        dp[2] = 1;
        for(int i = 3; i <= n; i++)
            dp[i] = dp[i - 2] + dp[i - 1];       
        return dp[n];
    }
    */
    
    //上述方法的优化，每次都只有到前两项，所以记录前两项。时间复杂度：O（n） 空间复杂度：O（1）
    public int Fibonacci(int n) {
        if(n <= 2) return 1;
        int a = 1,b = 1;
        for(int i = 3;i <= n; i++){
            int tmp = b;
            b = b + a;
            a = tmp;
        }
        return b;
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

BM63 跳台阶

dp[i]:第层台阶走法
dp[i] = dp[i - 1] +dp[i - 2]:第i层台阶走法=前一层走一步+前二层走两步的走法

public class Solution {
    /*
    //方法一：递归	时间复杂度O(n), 没有重复的计算(重复计算2^n)空间复杂度O（n）和递归栈的空间
    int[] tmp = new int[41];
    public int jumpFloor(int target) {
        if(tmp[target] != 0) return tmp[target];
        if(target == 1) {tmp[target] = 1; return 1;}
        if(target == 2) {tmp[target] = 2; return 2;}
        
        return tmp[target]  = jumpFloor(target - 1) + jumpFloor(target - 2);
    }
    */
    
    
    //方法二：动态规划 时间复杂度O(n),空间复杂度O(1)
    public int jumpFloor(int target) {
        if(target == 1) return 1;
        if(target == 2) return 2;
        int a = 1, b = 2;
        for(int i = 2; i < target; i++){
            int tmp = b;
            b += a;
            a = tmp;
        }
        return b;
    }    
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

BM64 最小花费爬楼梯

思路：
具体做法：

• step 1：可以用一个数组记录每次爬到第i阶楼梯的最小花费，然后每增加一级台阶就转移一次状态，最终得到结果。
• step 2：（初始状态） 因为可以直接从第0级或是第1级台阶开始，因此这两级的花费都直接为0.
• step 3：（状态转移） 每次到一个台阶，只有两种情况，要么是它前一级台阶向上一步，要么是它前两级的台阶向上两步，因为在前面的台阶花费我们都得到了，因此每次更新最小值即可，转移方程为：dp[i]=min(dp[i−1]+cost[i−1],dp[i−2]+cost[i−2])。

public class Solution {
     //时间复杂度：O(n)，其中nnn为给定的数组长度，遍历一次数组
	//空间复杂度：O(n)，辅助数组dp的空间
    public int minCostClimbingStairs (int[] cost) {
        if(cost.length < 3) return cost[0];
        int[] dp = new int[cost.length + 1];
        dp[1] = 0;
        for(int i = 2; i <= cost.length; i++)
            dp[i] = Math.min(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2]);    
        return dp[cost.length];
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

BM66 最长公共子串

public class Solution {
    /*
    //方法1：暴力枚举：时间复杂度O(n^2),运行时间过长，只跑过了70%，空间复杂度O(1)
    public String LCS (String str1, String str2) {
        // write code here
        int max = 0;
        int idx = 0;
        for(int i = 0;i < str1.length();i++){
            for(int j = i + 1; j < str1.length() + 1;j++){
                if(str2.contains(str1.substring(i, j))) 
                    if(max < j - i) 
                        {    
                            idx = i;
                            max = j - i;
                        }
            }
        }
        if(max == 0) return "-1";
        return str1.substring(idx,idx + max);
    }
    */
    
    /*
    方法二：动态规划
    step 1：可以用dp[i][j]表示在str1中以第i个字符结尾,在str2中以第j个字符结尾时的公共子串长度，
    step 2：遍历两个字符串填充dp数组，转移方程为：如果遍历到的该位两个字符相等，则此时长度等于两个前一位长度+1，dp[i][j]=dp[i−1][j−1]+1，如果遍历到该位时两个字符不相等，则置为0，因为这是子串，必须连续相等，断开要重新开始。
    step 3：每次更新dp[i][j]后，我们维护最大值，并更新该子串结束位置。
    step 4：最后根据最大值结束位置即可截取出子串。
    
    时间复杂度：O(mn)，其中m是str1的长度，n是str2的长度，遍历两个字符串所有字符
    空间复杂度：O(mn)，dp数组大小为m∗n
    */
    public String LCS (String str1, String str2) {
        int max = 0;
        int pos = 0;
        int[][] dp = new int[str1.length() + 1][str2.length() + 1];
        for(int i = 1; i <= str1.length();i++)
            for(int j = 1; j <= str2.length();j++){
                 dp[i][j] = str1.charAt(i - 1) == str2.charAt(j - 1)? dp[i - 1][j - 1] + 1 : 0;           
                 if(max < dp[i][j]) {
                     max = dp[i][j];
                     pos = i - 1; 
                }
            }
        
                 if(max == 0) return "-1";
                return str1.substring(pos - max + 1,pos + 1);
    }
     
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

BM67 不同路径的数目(一)

思路：dp[i][j]代表从起点到(i,j)的路径数量,到(i,j)只能从(i-1,j)和(i,j-1)到达。所以dp[i][j] = dp[i-1][j]+dp[i][j-1];
图示：54 dp数组变化

public class Solution {
    //时间复杂度O(m*n)
    //空间复杂度O(m*n)
    public int uniquePaths (int m, int n) {
        // write code here
        int[][] dp = new int[m][n];
        for(int i = 0;i< m;i++) dp[i][0] = 1;
        for(int j = 0;j < n;j++) dp[0][j] = 1;
        for(int i = 1; i < m; i++)
            for(int j = 1; j < n; j++){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                
            }
        return dp[m - 1][n - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

BM68 矩阵的最小路径和

思路：动态规划法
+ step 1：我们可以构造一个与矩阵同样大小的二维辅助数组，其中dp[i][j]表示以(i,j)位置为终点的最短路径和，则dp[0][0]=matrix[0][0]。
+ step 2：很容易知道第一行与第一列，只能分别向右或向下，没有第二种选择，因此第一行只能由其左边的累加，第一列只能由其上面的累加。
+ step 3：边缘状态构造好以后，遍历矩阵，补全矩阵中每个位置的dp数组值：如果当前的位置是(i，j)，上一步要么是(i−1,j)往下，要么就是(i,j−1)往右，那么取其中较小值与当前位置的值相加就是到当前位置的最小路径和，因此状态转移公式为dp[i][j]=min(dp[i−1][j],dp[i][j−1])+matrix[i][j]。
+ step 4：最后移动到(n−1,m−1))的位置就是到右下角的最短路径和
时间复杂度O(nm)，空间复杂度O(nm)

public class Solution {

    public int minPathSum (int[][] matrix) {
        // write code here
        int m = matrix.length,n = matrix[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = matrix[0][0];
        for(int i = 1; i < m; i++) dp[i][0] = matrix[i][0] + dp[i - 1][0];
        for(int j = 1; j < n; j++) dp[0][j] = matrix[0][j] + dp[0][j - 1];
        for(int i = 1;i < m;i++)
            for(int j  = 1;j < n; j++)
                dp[i][j] = matrix[i][j] + Math.min(dp[i - 1][j],dp[i][j - 1]);
            
        return dp[m - 1][n - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

BM69 把数字翻译成字符串

思路：

• step 1：用辅助数组dp表示前i个数的译码方法有多少种。
• step 2：对于一个数，我们可以直接译码它，也可以将其与前面的1或者2组合起来译码：如果直接译码，则dp[i]=dp[i−1]；如果组合译码，则dp[i]=dp[i−2]。
• step 3：对于只有一种译码方式的，选上种dp[i−1]即可，对于满足两种译码方式（10，20不能）则是dp[i−1]+dp[i−2]
• step 4：依次相加，最后的dp[length]即为所求答案。

时间复杂度：O(N) ，需要遍历一次数组
空间复杂度：O(N) ，需要声明一个状态数组记录f(x)

public class Solution {
    public int solve (String nums) {
        // write code here
        int[] dp = new int[nums.length()];
        if(nums.charAt(0) != '0')    dp[0] = 1;
        for(int i = 1; i < nums.length(); i++){  
               if(nums.charAt(i) != '0')
                   dp[i] += dp[i - 1];
                int tmp = Integer.parseInt(nums.substring(i - 1, i + 1));
                if(tmp >= 10 && tmp <= 26){
                    if(i == 1)
                        dp[i] += 1;
                    else  dp[i] += dp[i - 2]; 
                }
        }
        return dp[nums.length() - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

BM70 兑换零钱(一)

思路：
step 1：可以用dp[i]表示要凑出i元钱需要最小的货币数。
step 2：一开始都设置为最大值aim+1，因此货币最小1元，即货币数不会超过aim.
step 3：初始化dp[0]=0。
step 4：后续遍历1元到aim元，枚举每种面值的货币都可能组成的情况，取每次的最小值即可，转移方程为dp[i]=min(dp[i],dp[i−arr[j]]+1) .
时间复杂度：O(n⋅aim)，第一层遍历枚举1元到aim元，第二层遍历枚举n种货币面值
空间复杂度：O(aim)，辅助数组dp的大小

public class Solution {

    public int minMoney (int[] arr, int aim) {
        // write code here
        int[] dp = new int[aim + 1];
        //dp[i]表示凑齐i元最少需要多少货币数
        Arrays.fill(dp,aim + 1);
        dp[0] = 0;
        //遍历1-aim元
        for(int i = 1; i < aim + 1; i++){
            //每种面值的货币都要枚举
            for(int j = 0; j < arr.length; j++){
                if(arr[j] <= i)
                    //维护最小值
                    dp[i] = Math.min(dp[i],dp[i - arr[j]] + 1);
            }
        }
        //如果最终答案大于aim代表无解
        return dp[aim] == aim + 1 ? - 1 :dp[aim];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

BM71 最长上升子序列(一)

思路：
状态定义：dp[i]表示以下标i结尾的最长上升子序列的长度。
状态初始化：以任意下标结尾的上升子序列长度不小于1，故初始化为1。
状态转移：遍历数组中所有的数，再遍历当前数之前的所有数，只要前面某个数小于当前数，则要么长度在之前基础上加1，要么保持不变，取两者中的较大者。即dp[i]=Math.max(dp[i],dp[j]+1) 。

public class Solution {

    public int LIS (int[] arr) {
        if(arr.length < 1) return 0;
        int max = 0;
        int[] dp = new int[arr.length];
        Arrays.fill(dp,1);
        int res = 1;
        for(int i = 1; i < arr.length; i++){         
            for(int j = 0 ; j < i; j++){
                   if(arr[j] < arr[i])
                       dp[i] = Math.max(dp[i], dp[j] + 1);
                res = Math.max(res,dp[i]);
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

BM72 连续子数组的最大和

public class Solution {
    /*
    //暴力破解法：只过了50%。时间复杂度O(n^2),空间复杂度O(n)
    public int FindGreatestSumOfSubArray(int[] array) {
        int max = array[0];
        int sum = 0;
        for(int i = 0; i < array.length; i++){
            sum = 0;
            for(int j = i; j < array.length; j++){
                sum += array[j];
                max = Math.max(sum, max);
                
            }
        }
        return max;
        
    }
    */

    /*
    动态规划，设动态规划列表 dp，dp[i] 代表以元素 array[i] 为结尾的连续子数组最大和。
	状态转移方程： dp[i] = Math.max(dp[i-1]+array[i], array[i]);
	具体思路如下：
	1.遍历数组，比较 dp[i-1] + array[i] 和 array[i]的大小;
	2.为了保证子数组的和最大，每次比较 sum 都取两者的最大值;
	3.用max变量记录计算过程中产生的最大的连续和dp[i]；
    */
    public int FindGreatestSumOfSubArray(int[] array) {
        int[] dp = new int[array.length];
        dp[0] = array[0];
        int max = dp[0];
        for(int i = 1;i < array.length; i++){
            if(dp[i - 1] <= 0) dp[i] = array[i];
            else dp[i] = dp[i - 1] + array[i];
            max = Math.max(dp[i],max);
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

BM73 最长回文子串

思路：
算法流程：
维护一个布尔型的二维数组dp，dp[i][j]表示 i 到 j 的子串是否是回文子串
从长度0到字符串长度n进行判断
选定起始下标 i 和终止下标 j， i 和 j 分别为要比较的字符串的左右边界指针
从左右边界字符开始判断，即 A.charAt(i) == A.charAt(j)
当相等时，还要判断当前长度 c 是否大于1，不大于则表明只有两个字符的字符串，一个或两个字符肯定是回文串，如“11”
判断的长度大于1时，因为最左右的字符已经相等，因此取决于上一次的子串是否是回文子串, 如 “12121”
更新回文串的最大长度

public class Solution {
    /*方法一：中心扩展法 以该点或者该点相邻的点作为回文中心
    //时间复杂度 O(N^2)：平均需要遍历每个结点作为中心点，还需要从中心点向左右扩散比较。空间复杂度 O(1)：只用到常量
    public int getLongestPalindrome (String A) {
        if(A.length() <= 1)return 1;
        int max = 0;
        for(int i = 0; i < A.length() - 1;i++){
            int cur = Math.max(healper(i,i,A),healper(i,i+1,A));
            max = Math.max(cur,max);
        }
        return max;
        
    }
    public int healper(int left,int right,String A){
        int res = 0;
        while(left >=0 && right <= A.length() - 1){
            if(A.charAt(left) == A.charAt(right)){
                right++;
                left--;
                continue;
            }
            break;
        }
        return right - left + 1 -2;
    }
    */

    /*方法二：动态规划：
    时间复杂度 O(N^2)：N为字符串长度，平均判断的子串长度从0到N
    空间复杂度 O(N^2)：需要维护二维数组，代表转移方程的状态
    */
    public int getLongestPalindrome (String A) {
        boolean[][] dp = new boolean[A.length()][A.length()];
        int max = 0;
        for(int i =A.length() - 1;i >= 0;i--){//注意这里需要从右往左开始计算，因为1、2、3、4；要知道1~4的会问情况，就需要知道2，3回文情况，所以先要算里面
            for(int j = i;j < A.length();j++){
                if(A.charAt(i) == A.charAt(j) && (j - i  <= 1 || dp[i + 1][j - 1])){
                            dp[i][j] = true;
                            max = Math.max(j - i + 1,max);   
                    }
                }
               
            }
        return max;       
    }    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

BM74 数字字符串转化成IP地址

解法一：暴力枚举（可以AC但不推荐）
思路步骤：
四层循环，四个循环变量a,b,c,d
按照题目要求逐步对字符串进行截取，注意每次截取的起始索引
对截取完毕的段位进行合法性检查(合法性参考解法一思路)
合法则进行ip地址的拼接返回
时间复杂度：O(1),虽然for循环三层看起来有点吓人，但是本质上就是递归栈的展开,每次循环均<4,依然时常数级别。具体细节取决于有效的ip段
空间复杂度：O(1)，基于一般性，这里递归的栈层次数在常数范围。具体的，由于问题限制在有效 IP 段内，基于一般性，需要记录递归过程的信息，这个空间大小是递归树的高度 N

public class Solution {
    public ArrayList<String> restoreIpAddresses (String s) {
        ArrayList<String> res = new ArrayList<>();
        for(int i = 1; i < 4; i++){
            for(int j = 1; j < 4; j++){
                for(int m = 1; m < 4; m++){
                    for(int n = 1; n < 4; n++){
                        if(i + j + m + n  == s.length()){
                            String s1 = s.substring(0, i);
                            String s2 = s.substring(i, i + j);
                            String s3 = s.substring(i + j,i + j + m);
                            String s4 = s.substring(i + j + m, s.length());
                            if(check(s1)&& check(s2) && check(s3) && check(s4)){
                                String str = s1+"."+s2+"." + s3 + "." + s4;
                                res.add(str);
                            }
                        }
                    }
                }
            }
        } 
        return res;
    }
    private Boolean check(String str){
        if(Integer.valueOf(str) <= 255){
            if(str.charAt(0) != '0' || str.charAt(0) == '0' && str.length() == 1)
                return true;
        }
        return false;
    }
    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

题解思路：使用index表示下一个数在字符串s的起始位置，tmp表示已经切分的个数
递归边界： 已经分为4段了，且合法（tmp.size()==4）
回溯阶段： 将加入到tmp中的删除，且index要复原
判断合法： 1. index不能越界 2. num <=255 3 . 长度不为1且s[index] 不为0
时间复杂度：O(3^N) :每个循环都是常数级 N = 4
空间复杂度; O(N)

public class Solution {
    //回溯+剪纸
    public ArrayList<String> restoreIpAddresses (String s) {
         ArrayList<String> res = new ArrayList<String>();
        dfs(s, res, 1, 0);
        return res;
    }
     //记录分段IP数字字符串
    private String nums = "";
    //step表示第几个数字，index表示字符串下标
    public void dfs(String s, ArrayList<String> res, int step, int index){

        //四段都分完，最后一次为5时代表结束
        if(step == 5){
            //下标必须走到末尾
            if(index != s.length()) return ;
             res.add(nums);   
        }else{//最长遍历3位
            for(int  i = index; i < index + 3 && i < s.length(); i++){
                //截取该段
                String str = s.substring(index,i + 1);
                
                String temp = nums;
                //不能超过255且不能有前导0
                 if(Integer.parseInt(str) <= 255 && (str.length() == 1 || str.charAt(0) != '0')){
                    if(step < 4)//添加点
                        nums += str + ".";
                    else  nums += str; //递归查找下一个数字      
                    dfs(s,res,step + 1,i + 1);//回溯
                    nums = temp;
                }

            }
        }
        
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

BM78 打家劫舍(一)

思路：
对于第n个房间，我只有两种选择，要么愉，要么不偷。
愉的话,就得和n-2愉过的数值相加就是偷的最多的。
不偷的话:那就是n-1偷的最大值就是最后愉的数值。国此:第n间房偷的最天值就是∶
最后偷的最大值=Math.max(n-1)偷的最大值,(n-2)偷的最大值+当前房间的钱)

public class Solution {
    public int rob (int[] nums) {
        //不能简单的想成取奇数偶数
        int[] dp = new int[nums.length + 1];
        //长度为1只能偷第一家
        dp[1] = nums[0];
        //对于每家可以选择偷或者不偷
        for(int i = 2; i < dp.length;i++)
            dp[i] = Math.max(dp[i - 1],nums[i - 1] + dp[i - 2]);
            
        
        return dp[nums.length];
       
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

BM79 打家劫舍(二)

解题思路
状态定义：dp[i]dp[i]dp[i]表示到第i个房间为止，能偷到的最多的现金。
状态初始化：到第0个房间时，最多偷第0个房间的现金。到第1个房间时，最多偷第0个房间或第1个房间的现金，两者中取较大者。
状态转移：要么是前前家+当前，要么是前一家，取较大者。即dp[i]=Math.max(dp[i−1],dp[i−2]+nums[i])
首先在nums的0到n-2的房子中找，然后在1到n-1的房子中找，取两者中的较大者。

public class Solution {
    public int rob (int[] nums) { 
        int[] dp =  new int[nums.length + 1];
        dp[1] = nums[0];
        for(int i = 2;i < nums.length;i++){
            dp[i] = Math.max(nums[i - 1] + dp[i - 2],dp[i - 1]);
        }
        int m1 = dp[nums.length - 1];
        Arrays.fill(dp,0);
        dp[1] = 0;
        for(int i = 2;i < nums.length + 1; i++){
            dp[i] = Math.max(nums[i - 1] + dp[i - 2],dp[i - 1]);
        }
        int m2 = dp[nums.length];
        return m1 > m2 ? m1 : m2;    
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

BM80 买卖股票的最好时机(一)

思路：贪心，对于某一个天的股票的价格，我们加入我们在这天卖出，
那么假如我们需要最大的收益的话，
我们就需要在这一天前选择价格最低的一天买入，得到的差值就是我们的最大收益，然后维护一个最大值就行了。

public class Solution {
    public int maxProfit (int[] prices) {
        // write code here
        int res = 0;
        int min = prices[0];
        for(int i = 1;i < prices.length;i++){
            res = Math.max(prices[i] - min,res);// 然后维护获得的最大收益
            min = Math.min(prices[i],min);// 在遍历的过程中，不断更新我们的最小值
            
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13