Letcode-Top 100动态规划

1.简单-最大子数组和

1.动态规划

class Solution {
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        for(int i=1;i<nums.length;i++){
            if(dp[i-1]>0){
                dp[i]= dp[i-1] + nums[i];
            }else{
                dp[i]= nums[i];
            }

            if(dp[i]>max){
                max = dp[i];
            }
        }
        return max;
    }
}
// 首先是动态规划方程

//dp[i] 
// 前i-1位的最大值


//dp[i]>0
//dp[i-1]>0

//      f(n-1)+nums[i]                         f(n-1)>0
//f(n) 
//       nums[i]                          f(n-1)<0
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

2.简单-爬楼梯

1.动态规划

class Solution {
    public int climbStairs(int n) {

       int[] dp = new int[n+1];

        if(n==1){
            return 1;
        }

        dp[1]=1;

        if(n==2){
            return 2;
        }
        dp[2]=2;


        for(int i=3;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }

        return dp[n];
    }
}

// 第一步：首先动态规划方程
// 
// f(1)=1;
// f(2)=2;
// f(n) = f(n-1) + f(n-2)



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

3.简单-比特位计数

1.常规方法

class Solution {
    public int[] countBits(int n) {
        int[] totalNumber = new int[n+1];
        for(int i=1;i<=n;i++){
            totalNumber[i] = countNumber(i);
        }
        return totalNumber;
    }

    public int countNumber(int n){
    int one = 0;
     // 对每个数字判断位数
     while(n>0){
          // 数组换位 
          n= n&(n-1); 
          one++;
     }   
     return one;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.动态规划

class Solution {
    public int[] countBits(int n) {
        int[] dp = new int[n+1];
        int highBit = 0; 
        for(int i=1;i<dp.length;i++){
            if((i&(i-1))==0){
                highBit = i;
            }
            dp[i] = dp[i-highBit]+1;
        }
        return dp;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

4.简单-买卖股票的最佳时机

1.暴力破解的方式

public class Solution {
    public int maxProfit(int[] prices) {
        int maxprofit = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                int profit = prices[j] - prices[i];
                if (profit > maxprofit) {
                    maxprofit = profit;
                }
            }
        }
        return maxprofit;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.动态规划方式

class Solution {
    public int maxProfit(int[] prices) {
        // 买卖股票的最佳时机
        int[] dp = new int[prices.length];
        dp[0] = prices[0];
        int maxProfit = 0;

         //dp[i]表示截止到i，价格的最低点是多少   dp[i]=min(dp[i-1],nums[i])
        for(int i=1;i<prices.length;i++){
            dp[i] = dp[i-1]>prices[i] ?prices[i]:dp[i-1];
            maxProfit = prices[i]-dp[i-1]>maxProfit?prices[i]-dp[i-1]:maxProfit;
        }

        return maxProfit;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

5.中等-括号生成

1.动态规划
简单来说，在求N个括号的排列组合时，把第N种情况（也就是N个括号排列组合）视为单独拿一个括号E出来，剩下的N-1个括号分为两部分，P个括号和Q个括号，P+Q=N-1，然后这两部分分别处于括号E内和括号E的右边，各自进行括号的排列组合。由于我们是一步步计算得到N个括号的情况的，所以小于等于N-1个括号的排列组合方式我们是已知的（用合适的数据结构存储，方便后续调用，且在存储时可利用特定数据结构实现题目某些要求，如排序，去重等），且P+Q=N-1，P和Q是小于等于N-1的，所以我们能直接得到P个和Q个括号的情况，进而得到N个括号的结果！

楼主的算法思想很巧妙，赞一个~这个算法主要的基点就是将排列组合的情况分为了括号内和括号外这两种情况，且仅存在两种情况！至于为什么，原因在于楼主的算法的前提是单独拿出来的括号E的左边在N个括号所有排列组合情况中都是处于最左边，所以不存在括号位于括号E的左边的情况。因此，N-1个括号（拿出了括号E）仅可能分布于括号E内和括号E外，分为两种子情况讨论！ 这种思想还可以应用于其他类似的题的求解中，即怎样合理高效的利用前面步骤的计算结果得出当前步骤结果，从而得出最终结果。

class Solution {
    public List<String> generateParenthesis(int n) {
        ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
        if(n == 0){
            return result.get(0);
        }
        ArrayList<String> List0 = new ArrayList<String>();
        List0.add("");
        result.add(List0);

        ArrayList<String> list1 = new ArrayList<String>();
        list1.add("()");
        result.add(list1);

        for(int i = 2;i<=n;i++){
            ArrayList<String> temp = new ArrayList<String>();
            for(int j =0;j<i;j++){
                List<String> str1 = result.get(j);
                List<String> str2 = result.get(i-1-j);
                for(String s1:str1){
                    for(String s2:str2){
                        String e1 = "(" + s1 + ")" +s2;
                        temp.add(e1);
                    }

                }
            }
            result.add(temp);
        }
        return  result.get(n);
    }
}

// i+j = i-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

2.DFS

class Solution {
    List<String> res = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        dfs(n, n, "");
        return res;
    }

    private void dfs(int left, int right, String curStr) {
        if (left == 0 && right == 0) { // 左右括号都不剩余了，递归终止
            res.add(curStr);
            return;
        }

        if (left > 0) { // 如果左括号还剩余的话，可以拼接左括号
            dfs(left - 1, right, curStr + "(");
        }
        if (right > left) { // 如果右括号剩余多于左括号剩余的话，可以拼接右括号
            dfs(left, right - 1, curStr + ")");
        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22