【C++刷题】优选算法——动态规划第一辑

1.状态表示
	是什么？简答理解是dp表里的值所表示的含义
	怎么来的？
		题目要求
		经验+题目要求
		分析问题的过程中，发现重复子问题
2.状态转移方程
	dp[i]=......

细节问题：
	3.初始化
		控制填表的时候不越界
	4.填表顺序
		控制在填写当前状态的时候，所需要的状态已经填写好了
	5.返回值
		题目要求+状态表示

空间优化
	滚动数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1. 第 N 个泰波那契数

int tribonacci(int n)
{
    // 处理一些边界情况
    if(n < 3)
    {
        if(n == 0) return 0;
        else return 1;
    }

    // 1.创建dp表
    vector<int> dp(n + 1);
    // 2.初始化
    dp[0] = 0, dp[1] = 1, dp[2] = 1;
    for(int i = 3; i <= n; ++i)
    {
        // 3.填表
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
    }
    // 4.返回值
    return dp[n];
}
// 空间优化版本
int tribonacci(int n)
{
    int arr[3] = { 0,1,1 };
    if(n < 3) return arr[n];

    int ret = 0;
    for(int i = 3; i <= n; ++i)
    {
        ret = arr[0] + arr[1] + arr[2];
        arr[0] = arr[1], arr[1] = arr[2], arr[2] = ret;
    }
    return ret;
}
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

2. 三步问题

状态表示:
	经验+题目要求：以i位置为结尾来入手
	dp[i]: 表示到达i位置，一共有多少种方法
状态转移方程:
	基于i位置状态，跨一步到i位置，来划分问题
1
2
3
4
5

int waysToStep(int n)
{
    if(1 == n) return 1;
    else if(2 == n) return 2;
    else if(3 == n) return 4;

    // 1.dp数组
    vector<int> dp(n + 1);
    // 2.初始化
    dp[1] = 1, dp[2] = 2, dp[3] = 4;
    for(int i = 4; i <= n; ++i)
    {
        // 3.状态方程
        dp[i] = ((dp[i - 1] + dp[i - 2]) % 1000000007 + dp[i - 3]) % 1000000007;
    }
    // 4.返回值
    return dp[n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3. 使用最小花费爬楼梯

状态表示:
	经验+题目要求：以i位置为结尾来入手
	dp[i]: 表示i位置到下一步的最小花费
状态转移方程:
	dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
1
2
3
4
5

int minCostClimbingStairs(vector<int>& cost)
{
    // 1.dp数组
    vector<int> dp(cost.size());
    // 2.初始化
    dp[0] = cost[0]; dp[1] = cost[1];
    for (int i = 2; i < dp.size(); ++i)
    {
        // 3.状态转移方程
        dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
    }
    // 4.返回值
    return min(dp[dp.size() - 1], dp[dp.size() - 2]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

4. 解码方法

状态表示:
	经验+题目要求：以i位置为结尾来入手
	dp[i]: 表示以i位置为结尾时，解码方法的总数
状态转移方程:
1
2
3
4

int numDecodings(string s)
{
    // 0.边界情况
    if(s.size() < 2)
    {
        if(s[0] == '0') return 0;
        else return 1;
    }
    // 1.dp数组
    vector<int> dp(s.size(), 0);
    // 2.初始化
    if (s[0] == '0') dp[0] = 0;
    else dp[0] = 1;
    if (s[0] != '0' && s[1] != '0') dp[1] += 1;
    if (10 <= stoi(s.substr(0, 2)) && stoi(s.substr(0, 2)) <= 26) dp[1] += 1;

    for(int i = 2; i < dp.size(); ++i)
    {
        // 3.状态转移方程
        int num1 =0, num2 = 0;
        if(s[i] != '0') num1 = dp[i - 1];
        if(10 <= stoi(s.substr(i - 1, 2)) && stoi(s.substr(i - 1, 2)) <= 26) num2 = dp[i - 2];
        dp[i] = num1 + num2;
    }
    // 4.返回值
    return dp.back();
}
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

5. 不同路径

状态表示:
	经验+题目要求：以[i,j]位置为结尾来入手
	dp[i][j]: 表示以[i,j]位置为finish时，从start出发的不同路径数
状态转移方程:
	dp[i][j] = dp[i-1][j] + dp[i][j-1]
1
2
3
4
5

int uniquePaths(int m, int n)
{
    // 1.dp数组
    vector<vector<int>> dp(m, vector<int>(n));
    // 2.初始化
    for (int i = 0; i < m; ++i)
    {
        dp[i][0] = 1;
    }
    for (int i = 0; i < n; ++i)
    {
        dp[0][i] = 1;
    }
    // 3.状态转移方程
    for (int row = 1; row < m; ++row)
    {
        for (int col = 1; col < n; ++col)
        {
            dp[row][col] = dp[row - 1][col] + dp[row][col - 1];
        }
    }
    // 4.返回值
    return dp.back().back();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

6. 不同路径 II

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid)
{
    // 1.dp数组
    int m = obstacleGrid.size();
    int n = obstacleGrid[0].size();
    vector<vector<int>> dp(m, vector<int>(n));
    // 2.初始化
    for(int i = 0; i < m; ++i)
    {
        if(obstacleGrid[i][0] == 1)
            break;
        dp[i][0] = 1;
    }
    for(int i = 0; i < n; ++i)
    {
        if(obstacleGrid[0][i] == 1)
            break;
        dp[0][i] = 1;
    }
    // 3.状态转移方程
    for(int row = 1; row < m; ++row)
    {
        for(int col = 1; col < n; ++col)
        {
            if(obstacleGrid[row][col] == 1)
                continue;
            dp[row][col] = dp[row - 1][col] + dp[row][col - 1];
        }
    }
    // 4.返回值
    return dp.back().back();
}
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

7. 珠宝的最高价值

状态表示:
	经验+题目要求：以[i,j]位置为结尾来入手
	dp[i][j]: 表示到达[i,j]位置时所能得到的的最大价值
状态转移方程:
	dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + frame[i][j]
1
2
3
4
5

int jewelleryValue(vector<vector<int>>& frame)
{
    // 1.dp数组
    int row = frame.size();
    int col = frame[0].size();
    vector<vector<int>> dp(row, vector<int>(col));

    // 2.初始化
    dp[0][0] = frame[0][0];
    for(int i = 1; i < col; ++i)
    {
        dp[0][i] = dp[0][i - 1] + frame[0][i];
    }
    for(int i = 1; i < row; ++i)
    {
        dp[i][0] = dp[i - 1][0] + frame[i][0];
    }

    // 3.状态转移方程
    for(int i = 1; i < row; ++i)
    {
        for(int j = 1; j < col; ++j)
        {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i][j];
        }
    }

    // 4.返回值
    return dp.back().back();
}
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

8. 下降路径最小和

状态表示:
	经验+题目要求：以[i,j]位置为结尾来入手
	dp[i][j]: 表示到达[i,j]位置时所得到的最小下降路径和
状态转移方程:
	dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + frame[i][j]
1
2
3
4
5

    int minFallingPathSum(vector<vector<int>>& matrix)
    {
        // 1.dp数组
        int n = matrix.size();
        vector<vector<int>> dp(n, vector<int>(n));

        // 2.初始化
        for(int i = 0; i < n; ++i)
        {
            dp[0][i] = matrix[0][i];
        }

        // 3.状态转移方程
        for(int i = 1; i < n; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(j == 0)
                {
                    dp[i][j] = min(dp[i - 1][j], dp[i - 1][j + 1]) + matrix[i][j];
                }
                else if(j == n - 1)
                {
                    dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + matrix[i][j];
                }
                else
                {
                    dp[i][j] = min(min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i - 1][j + 1]) + matrix[i][j];
                }
            }
        }

        // 4.返回值
        int min_sum = dp[n - 1][0];
        for(int i = 1; i < n; ++i)
        {
            if(dp[n - 1][i] < min_sum) min_sum = dp[n - 1][i];
        }
        return min_sum;
    }
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

9. 最小路径和

状态表示:
	经验+题目要求：以[i,j]位置为结尾来入手
	dp[i][j]: 表示到达[i,j]位置时所得到的最小路径和
状态转移方程:
	dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
1
2
3
4
5

int minPathSum(vector<vector<int>>& grid)
{
    // 1.dp数组
    int m = grid.size();
    int n = grid[0].size();
    vector<vector<int>> dp(m, vector<int>(n));

    // 2.初始化
    dp[0][0] = grid[0][0];
    for(int i = 1; i < m; ++i)
    {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    for(int i = 1; i < n; ++i)
    {
        dp[0][i] = dp[0][i - 1] + grid[0][i];
    }

    // 3.状态转移方程
    for(int i = 1; i < m; ++i)
    {
        for(int j = 1; j < n; ++j)
        {
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        }
    }

    // 4.返回值
    return dp.back().back();
}
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

10. 地下城游戏

状态表示:
	经验+题目要求：以[i,j]位置为起点来入手
	dp[i][j]: 表示从[i,j]位置出发，到达终点，所需的最低初始健康点数
状态转移方程:
	dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
	dp[i][j] = max(1, dp[i][j]); // 细节处理，健康点数至少为1才能存活
1
2
3
4
5
6

int calculateMinimumHP(vector<vector<int>>& dungeon)
{
    // 1.dp数组
    int m = dungeon.size();
    int n = dungeon[0].size();
    vector<vector<int>> dp(m, vector<int>(n));

    // 2.初始化
    if(dungeon[m - 1][n - 1] < 0) dp[m - 1][n - 1] = 1 - dungeon[m - 1][n - 1];
    else dp[m - 1][n - 1] = 1;
    for(int i = n - 2; i >= 0; --i)
    {
        dp[m - 1][i] = dp[m - 1][i + 1] - dungeon[m - 1][i];
        dp[m - 1][i] = max(1, dp[m - 1][i]);
    }
    for(int i = m - 2; i >= 0; --i)
    {
        dp[i][n - 1] = dp[i + 1][n - 1] - dungeon[i][n - 1];
        dp[i][n - 1] = max(1, dp[i][n - 1]);
    }

    // 3.状态转移方程
    for(int i = m - 2; i >= 0; --i)
    {
        for(int j = n - 2; j >= 0; --j)
        {
            dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
            dp[i][j] = max(1, dp[i][j]);
        }
    }

    // 4.返回值
    return dp[0][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
32
33
34