下降路径最小和

数字三角形的变形题，线性dp

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
int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        vector<vector<int>> f(n, vector<int>(n));
        for (int i = 0; i < n; i ++)
        {
            f[0][i] = matrix[0][i];  
        }

        for (int i = 1; i < n; i ++)
        {
            for (int j = 0; j < n; j ++)
            {
                if (j == 0)
                    f[i][j] = min(f[i - 1][j], f[i - 1][j + 1]) + matrix[i][j];
                else if (j == n - 1)
                    f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + matrix[i][j];
                else    
                    f[i][j] = min({f[i - 1][j - 1], f[i - 1][j], f[i - 1][j + 1]}) + matrix[i][j];
            }
        }
        
        int minn = 0x3f3f3f3f;
        for (int i = 0; i < n; i ++)
        {
            minn = min(minn, f[n - 1][i]);
        }
        return minn;
    }

买卖股票的最佳时机 II

有限状态机模型

1
2
3
4
5
6
7
8
9
10
11
12
13
int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(2));
        f[0][0] = 0;
        f[0][1] = -prices[0];
        for (int i = 1; i < n; i ++)
        {
            f[i][0] = max(f[i - 1][1] + prices[i], f[i - 1][0]);
            f[i][1] = max(f[i - 1][1], f[i - 1][0] - prices[i]);
        }

        return f[n - 1][0];
    }

买卖股票的最佳时机

一边遍历一边维护一个到目前为止的最小值，再维护一个最大值，这样只用一遍循环就可以了

1
2
3
4
5
6
7
8
9
int maxProfit(vector<int>& prices) {
        int maxn = 0, minn = 0x3f3f3f3f;
        for (int i = 0; i < prices.size(); i ++)
        {
            minn = min(minn, prices[i]);
            maxn = max(maxn, prices[i] - minn);
        }
        return maxn;
    }