dp

发表于 | 更新于 | 评论数： | 阅读次数： | 阅读次数：

53. Maximum Subarray

f[i] 表示 所有 以第i个元素 结尾的子段 的最大值， 然后分两种情况 1. i前面没有元素( 0 ); 2.i前面有元素（以i - 1结尾的字段的最大值 f[i - 1]）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n);
        f[0] = nums[0];
        int ans = f[0];
        for (int i = 1; i < n; i++) {
            f[i] = max (f[i - 1], 0) + nums[i];
            ans = max (f[i], ans);
        }
        
        return ans;
    }
};

进一步思考， 发现 f[i] = max(f[i - 1], 0) + nums[i] 只用到了 f[i - 1] 的值

120. Triangle

1
2


63. Unique Paths II

1.状态表示f[i, j] 集合： 所有从起点走到（i, j）的路径
属性： 数量

2.状态计算：

  • 最后一步往下走： 从 f[i - 1, j] 到 f[i, j]
  • 最后一步往右走： 从 f[i, j - 1] 到 f[i, j]

那么 走到 (i， j) 的路径总数量 f[i, j] = f[i- 1, j] + f[i, j - 1]
这里要特判一下， 第一列（没有向右走的）和第一行 （没有向左走的）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int solve (vector<vector<int>>& g) {
    int n = g.size(), m = g[0].size();
    vector<vector<int>> f(n, vector<int>(m));

    for (int i = 0; i < n; i++) 
        for(int j = 0; j < m; j++) {
            if (g[i][j]) continue;
            if (!i && !j) f[i][j] = 1;
            if (i > 0) f[i][j] += f[i - 1][j];
            if (j > 0) f[i][j] += f[i][j - 1];
         }

    return f[n - 1][m - 1];

}

91. Decode Ways

198. House Robber

状态表示： 集合 ：f[i] 是以i结尾的数据段的
属性 ： max
状态计算： 最后一个元素有选或不选两种情况， f[i] = max(f[i - 2] + nums[i], f[i - 1])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (!n) return 0;
        vector<int> f(n);
        int ans = 0;
        if (n == 1) return nums[0];
        if (n == 2) return max(nums[0], nums[1]); //上面都是在考虑越界的问题
        f[0] = nums[0];
        f[1] = max(nums[0], nums[1]);
        for (int i = 2; i < n; i++) {           
            f[i] = max(f[i - 2] + nums[i], f[i - 1]);
            ans = max(ans, f[i]);
            
        }
        
        return ans;
        
    }
};

优化

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int rob(vector<int>& nums) {
        int pre = 0;
        int cur = 0;
        for (int i = 0; i < nums.size(); i++) {
            int temp = max(pre + nums[i], cur);
            pre = cur;
            cur = temp;
        }
        return cur;
    }
};

300. Longest Increasing Subsequence

以倒数第2个数是哪个 分成了i类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n);
        
        for (int i = 0; i < n; i++) {
            f[i] = 1;
            for (int j = 0; j < i; j++) 
                if (nums[i] > nums[j]) 
                    f[i] = max(f[i], f[j] + 1);
                            
        }
        int ans = 0;
        for (int i = 0; i < n; i++)  ans = max (ans, f[i]);
        
        return ans;
          
    }
};

72. Edit Distance

518. Coin Change 2

状态表示f[i, j]

  • 集合： 所有由前i种硬币凑出的总钱数等于j的凑法
  • 属性： 数量

状态计算：

  • f[i, j] = f[i - 1, j] + f[i - 1, j - c] + f[i - 1, j - 2*c] + ... + f[i - 1, j - k*c]
  • f[i, j - c] = f[i - 1, j - c] + f[i - 1, j - 2*c] + ... + f[i - 1, j - k*c]
    由上面两式可以得出 f[i, j] = f[i - 1, j] + f[i, j - c]

化成一维数组： f[j] = f[j] + f[j - c]

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

int change (int m, vector<int>& coins) {
    int n = coins.size();
    vector<int> f(m + 1);
    f[0] = 1;
    for (auto c : coins)
        for (int j = c; j <= m; j++) 
            f[j] += f[j - c];
        
    return f[m];


}
0%