无串线性问题

只有两个键的键盘

https://leetcode-cn.com/problems/2-keys-keyboard/

  1. int minSteps(int n){
  2.     int* dp = (int *)malloc(sizeof(int) * (n + 1));
  3.     dp[1] = 0;
  4.     for(int i = 2; i < n + 1; i++){
  5.         dp[i] = INT_MAX;
  6.         for(int j = 1; j * j <= i; j++){
  7.             if(i % j == 0){
  8.                 //顺序不能颠倒，否则超出INT_MAX
  9.                 // j个复制i/j次
  10.                 dp[i] = fmin(dp[i], dp[j] + i / j);
  11.                 // i/j个复制j次
  12.                 dp[i] = fmin(dp[i], dp[i / j] + j);
  14.             }
  15.         }
  16.     }
  17.     return dp[n];
  18. }

完全平方数

https://leetcode-cn.com/problems/perfect-squares/

  1. int numSquares(int n){
  2.     int dp[n + 1];
  3.     dp[0] = 0;
  4.     for(int i = 1; i < n + 1; i++){
  5.         int min = 10001;
  6.         for(int j = 1; j * j <= i; j++){
  7.             min = fmin(min, dp[i - j * j] + 1);
  8.         }
  9.         dp[i] = min;
  10.     }
  11.     return dp[n];
  12. }

单串问题

单串 LIS 系列

最长递增子序列

https://leetcode-cn.com/problems/longest-increasing-subsequence/

  1. int lengthOfLIS(int* nums, int numsSize){
  2.     int* dp = (int *)malloc(numsSize * sizeof(int));
  3.     //dp[i]表示以dp[i]结尾的最长递增子序列
  4.     dp[0] = 1;
  5.     int max = 1;
  6.     for(int i = 1; i < numsSize; i++){
  7.         dp[i] = 1;
  8.         for(int j = 0; j < i; j++){
  9.             if(nums[j] < nums[i]){
  10.                 dp[i] = (dp[i] > dp[j] + 1) ? dp[i] : dp[j] + 1;
  11.             }
  12.         }
  13.         max = max > dp[i] ? max : dp[i];
  14.     }
  15.     return max;
  16. }
  1. class Solution {
  2.     public int lengthOfLIS(int[] nums) {
  3.         int[] dp = new int[nums.length];
  4.         int max = 1;
  5.         dp[0] = 1;
  6.         for (int i = 1; i < nums.length; i++){
  7.             dp[i] = 1;
  8.             for (int j = 0; j < i; j++){
  9.                 if(nums[j] < nums[i]){
  10.                     dp[i] = Math.max(dp[j] + 1, dp[i]);
  11.                 }
  12.             }
  13.             max = Math.max(max, dp[i]);
  14.         }
  15.         return max;
  16.     }
  17. }

最长递增子序列的个数

https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence/

int findNumberOfLIS(int* nums, int numsSize){
    int* dp = (int *)malloc(numsSize * sizeof(int));
    int* count = (int *)malloc(numsSize * sizeof(int));
    //count[i] 为 dp[i] 对应的最长递增子序列个数
    dp[0] = count[0] = 1;
    int max = 1;
    for(int i = 1; i < numsSize; i++){
        dp[i] = count[i] = 1;
        for(int j = 0; j < i; j++){
            if(nums[i] > nums[j]){
                if(dp[i] == dp[j] + 1)
                    count[i] += count[j];
                else if(dp[i] < dp[j] + 1){
                    dp[i] = dp[j] + 1;
                    count[i] = count[j];
                }
            }
        }
        if(dp[i] > max)
            max = dp[i];
    }
    int result = 0;
    for(int i = 0; i < numsSize; i++){
        if(dp[i] == max)
            result += count[i];
    }
    return result;
}

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        //count[i] 为到 nums[i] 为止的最长递增子序列个数
        int[] count = new int[nums.length]; 
        Arrays.fill(dp, 1);
        Arrays.fill(count, 1);
        int max = 0;
        for(int i = 0; i < nums.length; i++){
            for(int j = 0; j < i; j++){
                if(nums[j] < nums[i]){
                    if(dp[j] + 1 > dp[i]){
                        dp[i] = dp[j] + 1;
                        count[i] = count[j];
                    }
                    else if(dp[j] + 1 == dp[i]){
                        count[i] = count[i] + count[j];
                    }
                }
            }
        max = Math.max(dp[i], max);
        }
        int ans = 0;
        for(int i = 0; i < nums.length; i++){
            if(dp[i] == max)
                ans += count[i];
        }
        return ans;
    }
}

俄罗斯套娃信封问题

https://leetcode-cn.com/problems/russian-doll-envelopes/

int compare(const void * a, const void * b);

int maxEnvelopes(int** envelopes, int envelopesSize, int* envelopesColSize){
    qsort(envelopes, envelopesSize, sizeof(int *), compare);
    int* dp = (int *)malloc(envelopesSize * sizeof(int));
    dp[0] = 1;
    int max = 1;
    for(int i = 1; i < envelopesSize; i++){
        dp[i] = 1;
        for(int j = 0; j < i; j++){
            if(**(envelopes + j) < **(envelopes + i) && *(*(envelopes + j) + 1) < *(*(envelopes + i) + 1)){
                dp[i] = (dp[i] > dp[j] + 1) ? dp[i] : dp[j] + 1;
            }
        }
        max = (dp[i] > max) ? dp[i] : max;
    }

    return max;
}

int compare(const void * a, const void * b){
    const int ** m = (const int **)a;
    const int ** n = (const int **)b;
    if(**m < **n)
        return -1;
    else if(**m == **n){
        if(*(*m + 1) < *(*n + 1))
            return 1;
        else return -1;
    }
    else return 1;
}

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        int n = envelopes.length;
        if(n == 0)
            return 0;
        Arrays.sort(envelopes, new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                if(a[0] != b[0])
                    return a[0] - b[0];
                else return b[1] - a[1];
            }
        });

        int dp[] = new int[n];
        Arrays.fill(dp, 1);
        int max = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < i; j++){
                if(envelopes[i][1] > envelopes[j][1])
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

最大子数组和系列

最大子序和

https://leetcode-cn.com/problems/maximum-subarray/

int maxSubArray(int* nums, int numsSize){
    int* dp = (int *)malloc(sizeof(int) * numsSize);
    //dp[i]表示以dp[i]结尾的最大子序和
    dp[0] = nums[0];
    int max = dp[0];
    for(int i = 1; i < numsSize; i++){
        if(dp[i - 1] < 0)
            dp[i] = nums[i];
        else
            dp[i] = dp[i - 1] + nums[i];
        max = (dp[i] > max) ? dp[i] : max;
    }
    return max;
}

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        if(n == 1)
            return nums[0];
        int[] dp = new int[n];
        dp[0] = nums[0];
        int max = dp[0];
        for(int i = 1; i < n; i++){
            if(dp[i - 1] < 0)
                dp[i] = nums[i];
            else dp[i] = dp[i - 1] + nums[i];
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

乘积最大子数组

https://leetcode-cn.com/problems/maximum-product-subarray/

int maxProduct(int* nums, int numsSize){
    int* max = (int *)malloc(sizeof(int) * numsSize);
    int* min = (int *)malloc(sizeof(int) * numsSize);
    int result, temp;
    result = max[0] = min[0] = nums[0];
    for(int i = 1; i < numsSize; i++){
        int a = nums[i];
        int b = nums[i] * max[i - 1];
        int c = nums[i] * min[i - 1];
        if(a > b){
            temp = a;
            a = b;
            b = temp;
        }
        if(b > c){
            temp = b;
            b = c;
            c = temp;
        }
        if(a > b){
            temp = a;
            a = b;
            b = temp;
        }
        max[i] = c;
        min[i] = a;
        result = (max[i] > result) ? max[i] : result;
    }
    return result;
}

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int min = nums[0];
        int max = nums[0];
        int ans = max;
        for(int i = 1; i < nums.length; i++){
            int temp = max; //由于下面要对max进行修改，需要暂存
            max = Math.max(max * nums[i], Math.max(min * nums[i], nums[i]));
            min = Math.min(temp * nums[i], Math.min(min * nums[i], nums[i]));
            ans = Math.max(ans, max);
        }
        return ans;
    }
}

打家劫舍系列

打家劫舍

https://leetcode-cn.com/problems/house-robber/

int rob(int* nums, int numsSize){
    int* dp = (int *)malloc(sizeof(int) * numsSize);
    dp[0] = nums[0];
    int max = dp[0];
    for(int i = 1; i < numsSize; i++){
        if(i == 1){
            dp[1] = nums[1] > dp[0] ? nums[1] : dp[0];
        }
        else if(i == 2){
            dp[2] = nums[2] + dp[0] > dp[1] ? nums[2] + dp[0] : dp[1];
        }
        else{
            dp[i] = nums[i] + dp[i - 2] > dp[i - 1] ? nums[i] + dp[i - 2] : dp[i - 1];
        }
        max = max > dp[i] ? max : dp[i];
    }
    return max;
}

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 0)
            return 0;
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = dp[0];
        for (int i = 1; i < n; i++){
            if(i >= 2){
                dp[i] = nums[i] + dp[i - 2];
                if(i >= 3){
                    dp[i] = nums[i] + Math.max(dp[i - 2], dp[i - 3]);
                }
            }
            else dp[i] = nums[i];
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

打家劫舍 II

https://leetcode-cn.com/problems/house-robber-ii/

int rob(int* nums, int numsSize){
    if(numsSize == 1)
        return nums[0];
    int* dp = (int *)malloc(sizeof(int) * numsSize);
    dp[0] = nums[0];
    int max = dp[0];

    //0 ~ numsSize-2
    for(int i = 1; i < numsSize - 1; i++){
        if(i > 2){
            dp[i] = nums[i] + dp[i - 2] > dp[i - 1] ? nums[i] + dp[i - 2] :  dp[i - 1];
        }
        else if(i == 1){
            dp[1] = nums[1] > dp[0] ? nums[1] : dp[0];
        }
        else if(i == 2){
            dp[2] = nums[0] + nums[2] > nums[1] ? nums[0] + nums[2] : nums[1];
        }
        max = dp[i] > max ? dp[i] : max;
    }

    //1 ~ numsSize-1
    dp[0] = nums[1];
    max = dp[0] > max ? dp[0] : max;
    for(int i = 1; i < numsSize - 1; i++){
        if(i > 2){
            dp[i] = nums[i + 1] + dp[i - 2] > dp[i - 1] ? nums[i + 1] + dp[i - 2] :  dp[i - 1];
        }
        else if(i == 1){
            dp[1] = nums[2] > dp[0] ? nums[2] : dp[0];
        }
        else if(i == 2){
            dp[2] = nums[1] + nums[3] > nums[2] ? nums[1] + nums[3] : nums[2];
        }
        max = dp[i] > max ? dp[i] : max;
    }
    return max;
}

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = dp[0];
        for (int i = 1; i < n - 1; i++){
            if(i >= 3){
                dp[i] = nums[i] + Math.max(dp[i - 2], dp[i - 3]);
            }
            else if(i >= 2){
                dp[i] = nums[i] + dp[i - 2];
            }
            else dp[i] = nums[i];
            max = Math.max(max, dp[i]);
        }

        if(n > 1){
            max = Math.max(max, nums[1]);
            for (int i = 2; i < n; i++){
                if(i >= 4){
                    dp[i] = nums[i] + Math.max(dp[i - 2], dp[i - 3]);
                }
                else if(i >= 3){
                    dp[i] = nums[i] + dp[i - 2];
                }
                else dp[i] = nums[i];
                max = Math.max(max, dp[i]);
            }
        }
        return max;
    }
}

双串问题

双串 LCS 系列

最长公共子序列

https://leetcode-cn.com/problems/longest-common-subsequence/

int longestCommonSubsequence(char * text1, char * text2){
    int a = strlen(text1);
    int b = strlen(text2);
    int dp[a + 1][b + 1];
    //从一个字符串为空开始考虑
    for(int i = 0; i < a + 1; i++){
        for(int j = 0; j < b + 1; j++){
            if(i == 0 || j == 0) 
                dp[i][j] = 0;
            else if(text1[i - 1] == text2[j - 1]){
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else{
                dp[i][j] = dp[i - 1][j] > dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1];
            }
        }
    }
    return dp[a][b];
}

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for(int i = 1; i < m + 1; i++){
            char a = text1.charAt(i - 1);
            for(int j = 1; j < n + 1; j++){
                if(a == text2.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[m][n];
    }
}

两个字符串的最小ASCII删除和

https://leetcode-cn.com/problems/minimum-ascii-delete-sum-for-two-strings/

int minimumDeleteSum(char * s1, char * s2){
    int a = strlen(s1);
    int b = strlen(s2);
    int dp[a + 1][b + 1];
    dp[0][0] = 0;
    for(int i = 1; i < a + 1; i++)
        dp[i][0] = dp[i - 1][0] + s1[i - 1];
    for(int i = 1; i < b + 1; i++)
        dp[0][i] = dp[0][i - 1] + s2[i - 1];
    for(int i = 1; i < a + 1; i++){
        for(int j = 1; j < b + 1; j++){
            if(s1[i - 1] == s2[j - 1])
                dp[i][j] = dp[i - 1][j - 1];
            else
                dp[i][j] = dp[i - 1][j] + s1[i - 1] < dp[i][j - 1] + s2[j - 1] ? dp[i - 1][j] + s1[i - 1] : dp[i][j - 1] + s2[j - 1];
        }
    }
    return dp[a][b];
}

class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        dp[0][0] = 0;
        for(int i = 1; i < m + 1; i++)
            dp[i][0] = s1.charAt(i - 1) + dp[i - 1][0];
        for(int j = 1; j < n + 1; j++)
            dp[0][j] = s2.charAt(j - 1) + dp[0][j - 1];
        for(int i = 1; i < m + 1; i++){
            for(int j = 1; j < n + 1; j++){
                if(s1.charAt(i - 1) == s2.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = Math.min(dp[i - 1][j] + s1.charAt(i - 1), dp[i][j - 1] +  s2.charAt(j - 1));
            }
        }
        return dp[m][n];
    }
}

最长重复子数组

https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/

int findLength(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int dp[nums1Size + 1][nums2Size + 1];
    int max = 0;
    for(int i = 1; i < nums1Size + 1; i++){
        for(int j = 0;  j < nums2Size + 1; j++){
            if(i == 0 || j == 0)
                dp[i][j] = 0;
            else if(nums1[i - 1] == nums2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = 0;
            max = max > dp[i][j] ? max : dp[i][j];
        }
    }
    return max;
}

class Solution {
    public int findLength(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        int[][] dp = new int[m + 1][n + 1];
        int max = 0;
        for(int i = 1; i < m + 1; i++){
            for(int j = 1; j < n + 1; j++){
                if(A[i - 1] == B[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                max = Math.max(max, dp[i][j]);
            }
        }
        return max;
    }
}

字符串匹配系列

编辑距离

https://leetcode-cn.com/problems/edit-distance/

int minDistance(char * word1, char * word2){
    int a = strlen(word1);
    int b = strlen(word2);
    int dp[a + 1][b + 1];
    dp[0][0] = 0;
    for(int i = 1; i < a + 1; i++)
        dp[i][0] = dp[i - 1][0] + 1;
    for(int i = 1; i < b + 1; i++)
        dp[0][i] = dp[0][i - 1] + 1;

    for(int i = 1; i < a + 1; i++){
        for(int j = 1; j < b + 1; j++){
            if(word1[i - 1] != word2[j - 1]){
                //增删
                dp[i][j] = dp[i - 1][j] < dp[i][j - 1] ? dp[i - 1][j] + 1 : dp[i][j - 1] + 1;
                //改
                dp[i][j] = dp[i][j] < dp[i - 1][j - 1] + 1 ? dp[i][j] : dp[i - 1][j - 1] + 1;
            }
            else
                dp[i][j] = dp[i - 1][j - 1];
        }
    }
    return dp[a][b];
}

背包问题

一和零（二维0-1背包）

https://leetcode-cn.com/problems/ones-and-zeroes/

int findMaxForm(char ** strs, int strsSize, int m, int n){
    int dp[strsSize + 1][m + 1][n + 1];
    memset(dp, 0, sizeof(dp));
    int zero, one;
    for(int i = 1; i < strsSize + 1; i++){
        zero = countZero(strs[i - 1]);
        one = strlen(strs[i - 1]) - zero;
        //注意循环从0开始，可以只包含一种物品
        for(int j = 0; j < m + 1; j++){
            for(int k = 0; k < n + 1; k++){
                //拿
                if(j - zero >= 0 && k - one >= 0)
                    dp[i][j][k] = dp[i - 1][j - zero][k - one] + 1;
                //不拿
                dp[i][j][k] = dp[i][j][k] > dp[i - 1][j][k] ? dp[i][j][k] : dp[i - 1][j][k];
            }
        }
    }
    return dp[strsSize][m][n];
}

int countZero(char * strs){
    int count = 0;
    for(int i = strlen(strs) - 1; i >= 0; i--){
        if(strs[i] == '0')
            count++;
    }
    return count;
}

最后一块石头的重量 II

https://leetcode-cn.com/problems/last-stone-weight-ii/

//要使最后一块石头的重量尽可能地小，需要在不超过 sum/2 的前提下尽可能地大。可以看作是背包容量为 sum/2 ，物品重量和价值均为 stones[i]，其中 dp[i+1][j] 表示前 i 个石头能否凑出重量 j

int lastStoneWeightII(int* stones, int stonesSize){
    int sum =  0;
    for(int i = 0; i < stonesSize; i++)
        sum += stones[i];
    int weight = sum / 2;
    int dp[stonesSize + 1][weight + 1];
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for(int i = 1; i < stonesSize + 1; i++){
        for(int j = 0; j < weight + 1; j++){ //当j = 0时，j < stones[i - 1]，不用提前初始化
            if(j < stones[i - 1])
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - stones[i - 1]];
        }
    }
    int max;
    for(int j = 0; j < weight + 1; j++){
        if(dp[stonesSize][j] == 1)
            max = j;
    }
    return sum - 2 * max;
}

分割等和子集（0-1背包、必须放满）

https://leetcode-cn.com/problems/partition-equal-subset-sum/

bool canPartition(int* nums, int numsSize){
    int sum = 0;
    for(int i = 0; i < numsSize; i++)
        sum += nums[i];
    int m = sum % 2;
    if(m != 0)
        return false;
    else{
        int dp[numsSize + 1][sum / 2 + 1];
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for(int i = 1; i < numsSize + 1; i++){
            for(int j = 0; j < sum / 2 + 1; j++){
                if(j < nums[i - 1])
                    dp[i][j] = dp[i - 1][j];
                else
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
            }
        }
        return dp[numsSize][sum / 2];
    }
}

零钱兑换（完全背包、必须放满）

https://leetcode-cn.com/problems/coin-change/

int coinChange(int* coins, int coinsSize, int amount){
    int dp[coinsSize + 1][amount + 1];
    for(int j = 1; j < amount + 1; j++)
        dp[0][j] = 10001;
    dp[0][0] = 0;
    for(int i = 1; i < coinsSize + 1; i++){
        for(int j = 0; j < amount + 1; j++){
            dp[i][j] = dp[i - 1][j];
            if(j - coins[i - 1] >= 0 && dp[i][j] > dp[i][j - coins[i - 1]] + 1)
                dp[i][j] = dp[i][j - coins[i - 1]] + 1;
        }
    }
    if(dp[coinsSize][amount] == 10001)
        return -1;
    else
        return dp[coinsSize][amount];
}

//优化为一维dp
int coinChange(int* coins, int coinsSize, int amount){
    int dp[amount + 1];
    dp[0] = 0;
    //初始化为原二维数组第一行
    for(int j = 1; j < amount + 1; j++)
        dp[j] = 10001;
    //循环不变，当前元素之前已修改为第i行，后为第i-1行
    for(int i = 1; i < coinsSize + 1; i++){
        for(int j = 1; j < amount + 1; j++){
            if(j - coins[i - 1] >= 0 && dp[j - coins[i - 1]] + 1 < dp[j])
                dp[j] = dp[j - coins[i - 1]] + 1;
        }
    }
    if(dp[amount] == 10001)
        return -1;
    else
        return dp[amount];
}

零钱兑换 II（完全背包、必须放满）

https://leetcode-cn.com/problems/coin-change-2/

int change(int amount, int* coins, int coinsSize){
    int dp[coinsSize + 1][amount + 1];   
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for(int i = 1; i < coinsSize + 1; i++){
        for(int j = 0;  j < amount + 1; j++){
            dp[i][j] = dp[i - 1][j];
            if(j - coins[i - 1] >= 0)
                dp[i][j] += dp[i][j - coins[i - 1]];
        }
    }  
    return dp[coinsSize][amount];
}

组合问题（求方案数）

组合总和 Ⅳ

https://leetcode-cn.com/problems/combination-sum-iv/solution/