leetcode 动态规划

发表于 | 更新于 | 分类于 ，
本文字数： 45k

322.零钱兑换

code

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount == 0:
            return 0
        count = len(coins)
        dp = [10005 for j in range(amount + 1)]
        dp[0] = 0
        for i in range(0, count):
            for j in range(amount + 1):
                if j >= coins[i]:
                    dp[j] = min(dp[j - coins[i]] + 1, dp[j])
        return dp[amount] if dp[amount] != 10005 else -1

53. 最大子序和

题解

如果直接求最大子序和是不好求的，这里的想法是这样的，用一个变量保存序列和，如果子序列和为负，那么它很不好，就清空，并将当前数字赋给这个和，反之就累加当前值，这个和在整个过程中，是从0增大，然后可能会减小到0，最大子序和一定出现在这个过程中；

code

1
2
3
4
5
6
class Solution(object):
    def maxSubArray(self, nums):
        # nums[i]表示以第i个数字结尾最大和
        for i in range(1, len(nums)):
            nums[i]= nums[i] + max(nums[i-1], 0)
        return max(nums)
1
2
3
4
5
6
7
8
9
10
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maxm = -float('inf')
        temp = nums[0]
        for x in nums:
            if temp > 0:
                temp += x
            else temp = x
            maxm = max(temp, maxm)
        return maxm

17.16. 按摩师

code

1
2
3
4
5
6
7
8
class Solution:
    def massage(self, nums: List[int]) -> int:
        n = len(nums)
        A,B = 0,0
        for i in range(n):
            # A是选择当前数字，B是不选
            A,B = B + nums[i], max(B,A)
        return max(A,B)

746. 使用最小花费爬楼梯

code

1
2
3
4
5
6
7
8
9
10
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        if len(cost) == 2: return max(cost[0],cost[1])
        dp = [float('inf') for i in range(len(cost) + 2)]
        count = len(cost)
        dp[0] = cost[0]
        dp[1] = cost[1]
        for i in range(2, count):
            dp[i] = min(dp[i - 1] + cost[i], dp[i - 2] + cost[i])
        return min(dp[count - 1], dp[count - 2])

474. 一和零

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        # 二维约束01背包
        zero,one = [],[]
        for str in strs:
            zero.append(str.count('0'))
            one.append(str.count('1'))
        dp = [[0 for i in range(101)] for j in range(101)]
        for i in range(len(strs)):
            for j in range(m,zero[i] - 1, -1):
                for k in range(n, one[i] - 1, -1):
                        dp[j][k] = max(dp[j - zero[i]][k - one[i]] + 1, dp[j][k])
        return dp[m][n]

300. 最长递增子序列

题解

第一种做法比较简单，也比较好想到，\(dp[i]\)表示第\(i\)个数字结尾的序列最长长度；

第二种做法：用一个数组暂存最长上升子序列\(a\)，每遍历到一个数字，用二分把这个数字查到\(a\)里面；给定序列[10,9,2,5,3,7,1]

当遍历到\(7\)的时候，\(a\)里面为[2,3,7]，当遍历到\(1\)时候，\(1\)插进去为[1,3,7]，这样并不会影响最长上升子序列的长度，并且，如果原序列中\(1\)后面还有长度超过\(3\)上升子序列，那么整个\(a\)会被更新成更长的上升子序列；

code

1
2
3
4
5
6
7
8
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = [1 for i in range(len(nums))]
        for i in range(len(nums)):
            for j in range(i + 1,len(nums)):
                if nums[i] < nums[j]:
                    dp[j] = max(dp[j], dp[i] + 1)
        return max(dp)

1027. 最长等差数列

题解

思路1：\(dp[i][k]\)，表示以\(a[i]\)结尾，公差为\(k\)的最长等差子列长度 在这种情况下，考虑状态转移，仅需要枚举任意两元素\(i、j\)，考虑\(j\)到\(i\)的状态转移；

思路2：\(dp[i][j]\)，表示以\(a[j]、a[i]\)作为最长等差子列结尾两元素（也就是公差是\(a[i] - a[j]\)）的最长长度； 这种情况下，暴力的想，可以枚举\(k\)，使\(k、j、i\)三个元素成为一个等差数列，然后考虑状态转移，但这样复杂度很高，然而这个过程是贪心的，即这个\(k\)越大越好（但需要小于\(j\)），我们可以这样做：每一次枚举\(j\)结束后更新answer，并且mp[a[j]] = j

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int d[2005][20010];
class Solution {
public:
    int longestArithSeqLength(vector<int>& A) {
        const int N = A.size();
        memset(d,0,sizeof(d));
        int ans = 2;
        for(int i=0;i<N;++i){
            d[i][10000] = 1;
            for(int j=0;j<i;++j){
                int diff = A[i] - A[j] + 10000;
                int& r = d[i][diff];
                r = max(r,max(2,d[j][diff]+1));
                ans = max(ans,r);
            }
        }
        
        return ans;
    }
};
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
int d[2005][2005];
int idx[10010];
class Solution {
public:
    int longestArithSeqLength(vector<int>& A) {
        const int N = A.size();
        memset(d,0,sizeof(d));
        memset(idx,0xcf,sizeof(idx));
        int ans = 2;
        for(int i=0;i<N;++i){
            d[i][i] = 1;
            for(int j=0;j<i;++j){
                int& r=d[j][i];
                if(j == 0){
                    r = max(r,2);
                }else{
                    int x = 2 * A[j] - A[i];
                    if(x < 0 || idx[x] < 0){
                        r = max(r,2);
                    }else{
                        r = max(r,d[idx[x]][j]+1);
                    }
                }
                ans = max(ans,r);
                idx[A[j]] = j;
            }
            
        }
        
        return ans;
    }
};

978. 最长湍流子数组

code

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 maxTurbulenceSize(vector<int>& arr) {
        int ans = 1;
        int sum[2] = {1,1};
        for (int i = 1; i < arr.size(); i++) {
            if (i % 2) {
                if (arr[i] < arr[i - 1])sum[0]++, sum[1] = 1;
                else if(arr[i] > arr[i - 1])sum[1]++, sum[0] = 1; 
                else sum[0] = sum[1] = 1;
            }
            else if (!(i % 2)) {
                if (arr[i] > arr[i - 1])sum[0]++,sum[1] = 1;
                else if(arr[i] < arr[i - 1])sum[1]++,sum[0] = 1;
                else sum[0] = sum[1] = 1;
            }
            ans = max(ans,max(sum[0], sum[1]));
        }
        return ans;
    }
};

787. K 站中转内最便宜的航班

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        int dp[103][103];
        memset(dp, 0x3f3f3f3f, sizeof(dp));
        for (auto &x: flights) 
            if (x[0] == src)
                dp[x[1]][0] = x[2];
        for (int i = 0; i <= K; i++)
            dp[src][i] = 0;
        for (int k = 1; k <= K; k++) 
            for (auto &x: flights)
                if (dp[x[0]][k - 1] != 0x3f3f3f3f)
                    dp[x[1]][k] = min(dp[x[1]][k], dp[x[0]][k - 1] + x[2]);
        return dp[dst][K] == 0x3f3f3f3f?-1:dp[dst][K];
    }
};

1641. 统计字典序元音字符串的数目

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int countVowelStrings(int n) {
        int dp[7];
        for (int i = 1; i <= 5; i++)
            dp[i] = 1;
        for (int i = 1; i <= n - 1; i++) {
            int sum = 0;
            for (int j = 1; j <= 5; j++) {
                sum += dp[j];
                dp[j] = sum;
            }
        }
        int ans = 0;
        for (int i = 1; i <= 5; i++)
            ans += dp[i];
        return ans;
    }
};

343. 整数拆分

题解

\(dp[i]\)表示对于整数\(i\)拆分成若干整数之后的最大乘积，那么显然的，\(dp[i] = max(dp[i],dp[i - k] * k)(1\leq k\leq i - 1)\)；但是这不包括所有情况，\(dp[6] = dp[3] * 3 = 6\)，而\(dp[6] = 3 * (6 - 3) = 9\)更大；即\(dp[i] = max(dp[i], j * (i - j))\)；

code

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int integerBreak(int n) {
        int dp[60];
        memset(dp, 0, sizeof(dp));
        dp[1] = 1;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j < i; j++) {
                dp[i] = max(dp[i], max(j * (i - j), dp[j] * (i - j)));
            }
        return dp[n];
    }
};

467. 环绕字符串中唯一的子字符串

题解

这题第一次做，把自己给绕进去了，甚至没读懂题目；

题目让我们求\(p\)中有多少个种连续的字符串，连续即题目中所谓的连续；

如果不考虑多少种，仅仅问多少个，这就相当于问有多少个连续子区间，这个比较好求；但这里要求不重复；

定义\(dp[i]\)，表示以字符\(i\)结尾的最大连续子串，这样就可以去除重复；比如对于abcbc，当遍历到第一个c，\(dp['c'] = 6\)，对于后面的bc，显然他已经包含在dp['c']=6的情况之内了；还可以尝试模拟这个字符串的情况：abczab；

  1. 这个题解里的图的变化情况解释的很好：https://leetcode-cn.com/problems/unique-substrings-in-wraparound-string/solution/dong-tai-gui-hua-c-by-lcoder55455-y3px/
  2. 这篇博客对于滑动窗口写的很好：https://leetcode-cn.com/problems/unique-substrings-in-wraparound-string/solution/xi-fa-dai-ni-xue-suan-fa-yi-ci-gao-ding-qian-zhui-/

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int findSubstringInWraproundString(string p) {
        if (p == "")return 0;
        int dp[30];
        memset(dp, 0, sizeof(dp));
        dp[p[0] - 'a'] = 1;
        int sum = 1;
        for (int i = 1; i < p.length(); i++) {
            if (p[i] == p[i - 1] + 1 || p[i - 1] == p[i] + 25)
                sum ++;
            else sum = 1;
            dp[p[i] - 'a'] = max(dp[p[i] - 'a'], sum);
        }
        int ans = 0;
        for (int i = 0; i < 26; i++)
            ans += dp[i];
        return ans;
    }
};

357. 计算各个位数不同的数字个数

非常多种写法

1314. 矩阵区域和

650. 只有两个键的键盘

1105. 填充书架

题解

\(dp[i]\)表示\(i\)本书的最小高度，也就是以第\(i\)本书作为最后一层最后一本书，达到的最小高度，我们已经知道前面\(1\)到\(i-1\)本书能达到的最小高度，只要枚举最后一层的书，最后一层一定是包含\(i\)之前的若干本，并且厚度有上限，我们就可以从中更新出最小高度；

code

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 minHeightShelves(vector<vector<int>>& books, int shelf_width) {
        int n = books.size();
        vector<int> dp(n+1,1000*1000);
        dp[0] = 0;
        for(int i = 1; i <=n; i++) {
            int j = i;
            int tmpWidth = 0;
            int h = 0;
            while(j) {
                tmpWidth += books[j - 1][0];                
                if(tmpWidth > shelf_width) break;
                h = max(h, books[j - 1][1]);
                dp[i] = min(dp[i], dp[j-1] + h);
                j--;
            }
        }
        return dp[n];
    }
};