动态规划

发表于 分类于 阅读次数：
本文字数： 7k 阅读时长 ≈ 6 分钟

动态规划

最大子序和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
*/
class Solution {
public: 
    int maxSubArray(vector<int>& nums) {
        //状态表示 dp[i] 最长子数组
        //状态计算 dp[i] = max(dp[i-1],0)+num[i];
        
        int res = INT_MIN,last = 0;
        for(int i = 0; i < nums.size(); i++){
            int now = max(last,0) + nums[i];
            res = max(res, now);
            last = now;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int res = dp[0];
        for(int i = 1; i< dp.length; i++){
            dp[i] = Math.max(dp[i-1],0)+nums[i];
            if(res < dp[i])
                res = dp[i];
        }
       return res;
    }
}

三角形最小路径和

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
52
53
54
55
56
57
58
59
60
61
62
/*
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）
*/
class Solution {
public:
    int minimumTotal(vector<vector<int>>& nums) {
        //状态表示：dp[i][j] 从头到i j点的最小路径和
        //状态计算：右边下if(j>0)dp[i][j] = min(dp[i][j], dp[i-1][j-1]+num[i][j]);
        //状态     左边下if(j<i)dp[i][j] = min(dp[i][j], dp[i-1][j] +num[i][j]);
        
        int n = nums.size();
        vector<vector<long long >>dp(n,vector<long long> (n));
        dp[0][0] = nums[0][0];
        for(int i = 1; i < n; i++){
            for(int j = 0; j <= i ; j++)
            {
                dp[i][j] = INT_MAX;
                if(j>0)dp[i][j] = min(dp[i][j], dp[i-1][j-1]+num[i][j]);
                if(j<i)dp[i][j] = min(dp[i][j], dp[i-1][j] +num[i][j]);
            }
        }
        long long res = INT_MAX;
        for(int i = 0; i < n; i ++)
            res = min(res, dp[n-1][i]);
    }
};

//滚动数组
class Solution {
public:
    int minimumTotal(vector<vector<int>>& nums) {
        //状态表示：dp[i][j] 从第一层开始 走道 i层 j个 的最小路径和
        //状态计算：右边下来（j>0）(dp[i][j] = min(dp[i][j],dp[i-1][j-1]+nums[i][j])
        //         左边下来（j < i）(dp[i][j] = min(dp[i][j],dp[i-1][j] + nums[i][j]))
        
        int n = nums.size();
        vector<vector<long long>>dp(2, vector<long long> (n));
        dp[0][0] = nums[0][0];
        for(int i = 1; i < n; i++){
            for(int j = 0; j <= i; j++)
            {
                dp[i & 1][j] = INT_MAX;
                if(j>0) dp[i & 1][j] = min(dp[i & 1][j],dp[i- 1 & 1][j-1]+nums[i][j]);
                if(j<i) dp[i & 1][j] = min(dp[i & 1][j],dp[i- 1 & 1][j] + nums[i][j]);
            }
        }
        long long res = INT_MAX;
        for(int i = 0; i < n; i++)
            res = min(res, dp[n-1 & 1][i]);
        return res;
    }
};
1
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
34
35
36
37
/**一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
说明：m 和 n 的值均不超过 100。
示例 1:
输入:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
*/
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obj) {
        int n = obj.size(), m = obj[0].size();
        vector<vector<long long> dp(n,vector<long long>(m));
        
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++){
                if(obj[i][j]) continue;
                if(!i && !j) dp[i][j] = 1;
                if(i > 0) dp[i][j] += dp[i-1][j];
                if(j > 0) dp[i][j] += dp[i][j-1];
            }
        }
        return dp[n-1][m-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
/**给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
*/
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        // 2 的映射 abc 存到临时表+固定表中  固定表 = 临时表
        if(digits.empty()) return vector<string>();
        string str[8] = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        
        vector<string>ch(1,"");
        for(auto x : digits) {// 2 3
            vector<string>now;
            for(auto s : str[x - '2']){ // 123 456
                for(auto z : ch)
                	now.push_back(z+s); 
            }
            ch = now;
        }
        return ch;
    }
};

单词搜索

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
/**
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.
*/
class Solution {
public:
    int m , int n;
    int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};
     bool exist(vector<vector<char>>& board, string word) {
         if(!board.empyt() || board[0].empty()) return false;
         m = board.size(), n = board[0].size();
         
         for(int i = 0; i < n; i++){
             for(int j = 0; j < m; j++){
                 if(dfs(board,i,j,word,len))
                     return true;
             }
         }
         return false;
     }
    bool dfs(vector<vector<char>>& board, int x, int y, stirnt& word, int len){
        if(board[i][j] != word[len]) return false;
        if(len == word.size() -1) return true;
        
        board[i][j] = '*';
        for(int i = 0 ; i< 4; i++)
        {
            int xi = x + dx[i], yi = y + dy[i];
            if(xi >=0 && xi < n && yi >=0 && yi < n){
                if(dfs(board,xi,yi,word,len+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
class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        if(nums == null || len == 0) return 0;

        // fx i 不选num【i】
        // px i 选num【i】
        int[] fx = new int[len+1];
        int[] px = new int[len+1];

        px[0] = 0;
        //状态：
        for(int i = 1; i <= len ; i++){
            fx[i] = Math.max(fx[i-1],px[i-1]);
            px[i] = fx[i-1]+ nums[i-1] ;
            
        }
        return Math.max(fx[len],px[len]);
    }
}

##

最长上升子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int lengthOfLIS(int[] nums) {
        
        int len = nums.length;
        int[] f = new int[len];
        int res = 0;
        for(int i = 0; i < len; i++){
            
            f[i] = 1;
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j])
                    f[i] = Math.max(f[i],f[j]+1);
            }
            res = Math.max(res,f[i]);
        }
        return res;
    }
}
相关文章
0%