动态规划学习

        在进行算法题练习和一些题目中发现关于动态规划的内容较多，觉得有必要系统的学习和练习一下 于是参照bilbilUP主 英雄哪里出来 的动态规划50题和LeetKoke网站进行学习和练习

一 概述

       动态规划 是一个有限状态自动机 可以抽象为一个有向无环图 有起始节点 终止节点 每一个节点表示一个状态 任何一个非初始节点都可以从其他节点转移过来(状态转移) 而如何设计状态就是解决动态规划问题的关键

       本质是空间换时间 利用空间的缓存能力来换取计算机的CPU消耗  

最简单的例子就是递归(斐波那契数列)

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给定n 求f(n)的值

int fib(int n) {
    if(n == 0){return 0;}
    else if(n == 1){return 1;}
    return fib(n-1) + fib(n-2);
    
}

二 解题步骤

1. 设计状态
2. 确定状态转移方程
3. 确定初始状态
4. 执行状态转移
5. 计算最终的解

三 动态规划使用的判断

节点抽象后 关系用边表示 简单进行一次拓扑排序 如何发现有环 则一定不是动态规划

同样 动态规划问题也和数据范围有关系 如果数据量比较大 大概率不是动态规划(因为无法映射到数组中) 就有可能是暴力搜素或者贪心算法[动态规划靠经验]

四 相关题解

1 线性DP

   [1] 递推

  (1) 青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶，求该青蛙跳上一个n级的台阶总共有多少种跳法

答案需要取模1e9+7(1000000007) 如计算初始结果为：100000008 请返回1

#define mod 1000000007

int f[110];

int numWays(int n) {
    f[0] = f[1] = 1;
    for (int i = 2; i <= n; ++i) {
        f[i] = (f[i - 1] + f[i - 2]) % mod;
    }
    return f[n];
}

int main() {

    int n;
    scanf("%d",&n);
    printf("%d",numWays(n));

    return 0;
}

(2) 爬楼梯问题

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

int climbStairs(int n) {
    int f[46];
    f[0] = f[1] = 1;
    for(int i = 2;i<=n;i++){
        f[i] = f[i-1] + f[i-2];
    }
    return f[n];
}

(3) 将数字变成0的操作方案

给你一个非负数num,请你返回将它变成0所需的步数，如果当前数字是偶数，你需要它除以2，否则，减去1.

 非动态规划解法

int numberOfSteps(int num) {
    int n = 0;
    while(num != 0){
        if(num%2 == 0){
            num /=2;
            n++;
        }
        else{
            num -=1;
            n++;
        }
    } 
    return n;
}

动态规划解法

int numberOfSteps(int num) {
   int f[1000001];
   for(int i = 0;i<=num;i++){
     if(i % 2 == 1){
         f[i] = f[i-1] + 1;
      }else{
         f[i] = f[i/2] + 1;
      }
      return f[num];
   }
}

(4)爬楼梯的最小成本

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。

每当爬上一个阶梯都要花费对应的体力值，一旦支付了相应的体力值，就可以选择向上爬一个阶梯或者爬两个阶梯。

请找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

int min(int a,int b){
   return a<b?a:b;
}
int minCostClimbingStairs(int* cost, int costSize){
   int f[1024];
   f[0] = f[1] = 0;
   for(int i = 2;i<=costSize;i++){
    f[i] = min(f[i-1]+cost[i-1],f[i-2]+cost[i-2]);
   }   
   return f[costSize];
}

 [2] 状态转移

(1) 打家劫舍

一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响小偷偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组 nums ，请计算 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

int max(int a,int b){
    return a>b?a:b;
}

int rob(int* nums, int numsSize){
   int f[numsSize+1];
   f[0] = nums[0];
   for(int i = 1;i<numsSize;i++){
    if(i == 1){
        f[1] = max(nums[0],nums[1]);
    }
    else{
         f[i] = max(f[i-1],f[i-2]+nums[i]);
     } 
  }
      return f[numsSize-1];
}

(2) 打家劫舍Ⅱ

一个专业的小偷，计划偷窃一个环形街道上沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组 nums ，请计算 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

int max(int a,int b){
    return a>b?a:b;
}

int rob(int* nums, int numsSize){
   int dp[numsSize+1][numsSize+1];
   if(numsSize == 1){
     return nums[0];
   }else if(numsSize == 2){
     return max(nums[0],nums[1]);
   }
   dp[0][0] = 0;
   dp[0][1] = nums[0];

   for(int i = 1;i < numsSize;i++){
    for(int j = 0;j<2;j++){
    if(i == 1){
        if(j == 0){ dp[i][j] = nums[1];}
        else{dp[i][j] = nums[0];}
    }
    else if(i == numsSize-1 && j == 1){
        dp[i][j] = dp[i-1][j];
    }
    else{ dp[i][j] = max(dp[i-1][j],dp[i-2][j]+nums[i]);}
       
  }
}
      return max(dp[numsSize-1][0],dp[numsSize-1][1]);
}

(3)解码方法

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

"1" -> 'A'
"2" -> 'B'
...
"25" -> 'Y'
"26" -> 'Z'

然而，在 解码 已编码的消息时，你意识到有许多不同的方式来解码，因为有些编码被包含在其它编码当中（"2" 和 "5" 与 "25"）。

例如，"11106" 可以映射为：

• "AAJF" ，将消息分组为 (1, 1, 10, 6)
• "KJF" ，将消息分组为 (11, 10, 6)
• 消息不能分组为  (1, 11, 06) ，因为 "06" 不是一个合法编码（只有 "6" 是合法的）。

注意，可能存在无法解码的字符串。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。如果没有合法的方式解码整个字符串，返回 0。

题目数据保证答案肯定是一个 32 位 的整数。

int numDecodings(char* s) {
    int len = strlen(s);
    if (len == 0 || s[0] == '0') return 0; 

    int dp[len + 1];
    dp[0] = 1; 
    dp[1] = (s[0] == '0') ? 0 : 1; 

    for (int i = 2; i <= len; i++) {
        int oneDigit = (s[i - 1] != '0'); 
        int twoDigits = (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6')); 

        dp[i] = oneDigit * dp[i - 1]; 
        if (twoDigits) {
            dp[i] += dp[i - 2]; 
        }
    }

    return dp[len]; 
}

（4）获取生成数组中的最大值

给你一个整数 n 。按下述规则生成一个长度为 n + 1 的数组 nums ：

• nums[0] = 0
• nums[1] = 1
• 当 2 <= 2 * i <= n 时，nums[2 * i] = nums[i]
• 当 2 <= 2 * i + 1 <= n 时，nums[2 * i + 1] = nums[i] + nums[i + 1]

返回生成数组 nums 中的 最大 值。

示例 1：

输入：n = 7
输出：3
解释：根据规则：
  nums[0] = 0
  nums[1] = 1
  nums[(1 * 2) = 2] = nums[1] = 1
  nums[(1 * 2) + 1 = 3] = nums[1] + nums[2] = 1 + 1 = 2
  nums[(2 * 2) = 4] = nums[2] = 1
  nums[(2 * 2) + 1 = 5] = nums[2] + nums[3] = 1 + 2 = 3
  nums[(3 * 2) = 6] = nums[3] = 2
  nums[(3 * 2) + 1 = 7] = nums[3] + nums[4] = 2 + 1 = 3
因此，nums = [0,1,1,2,1,3,2,3]，最大值 3

int getMaximumGenerated(int n) {
    int nums[110];
    nums[0] = 0;
    nums[1] = 1;
    for(int i = 1;i<=n;i++){
    if(2*i >= 2 && 2*i <=n){
      nums[2*i] = nums[i];
    }
    if(2 <= 2*i+1 && 2*i+1 <= n){
      nums[2 * i + 1] = nums[i] + nums[i + 1];
    }
  }
    int v = 0;
    for(int i = 1;i<=n;i++){
        if(v < nums[i]){
            v = nums[i]; 
        }
    }
    return v; 
}

(5)分割数组以得到最大值

给你一个整数数组 arr，请你将该数组分隔为长度 最多 为 k 的一些（连续）子数组。分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。

返回将数组分隔变换后能够得到的元素最大和。本题所用到的测试用例会确保答案是一个 32 位整数。

示例 1：

输入：arr = [1,15,7,9,2,5,10], k = 3
输出：84
解释：数组变为 [15,15,15,9,10,10,10]

示例 2：

输入：arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
输出：83

示例 3：

输入：arr = [1], k = 1
输出：1

int max(int a,int b){
    return a > b ? a : b;
}

int maxSumAfterPartitioning(int* arr, int arrSize, int k) {
    int maxv,cnt;
    int dp[500];
    for(int i = 0;i < arrSize; i++){
       maxv = 0;
       dp[i] = 0;
       cnt = 0;
       for(int j = i;j>=0;--j){
        if(arr[j] > maxv){
            maxv = arr[j];
        }
        ++cnt;
        if(cnt > k){
            break;
        }
        if(j){
            dp[i] = max(dp[i],dp[j-1] + cnt*maxv);
        }else{
            dp[i] = max(dp[i],cnt*maxv);
        }
       }
    }
      return dp[arrSize-1];
}

(6)单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

bool wordBreak(char* s, char** wordDict, int wordDictSize) {
    int dp[350];
    memset(dp,0,sizeof(dp));
    int i,j,k,l;
    int n = strlen(s);
    for(i = 0;i<n;i++){
        for(j = 0;j<wordDictSize;j++){
            l = strlen(wordDict[j]);
            if(i-l+1 < 0){ continue;}
            if(i-l != -1 && ! dp[i-l]){ continue;}
            for(k = 0; k<l ;k++){
                if(s[i-l+1+k] != wordDict[j][k]){
                    break;
                }
            }
            if(k == l){
                dp[i] = 1;
                break;
            }
        } 
    }
         return dp[i-1];
}

[3] 前缀和

(1) 哪种连续子字符串更长

给你一个二进制字符串 s 。如果字符串中由 1 组成的 最长 连续子字符串 严格长于 由 0 组成的 最长 连续子字符串，返回 true ；否则，返回 false 。

• 例如，s = "110100010" 中，由 1 组成的最长连续子字符串的长度是 2 ，由 0 组成的最长连续子字符串的长度是 3 。

注意，如果字符串中不存在 0 ，此时认为由 0 组成的最长连续子字符串的长度是 0 。字符串中不存在 1 的情况也适用此规则。

int max(int a,int b){
    return a>b?a:b;
}

bool checkZeroOnes(char* s) {
    int dp[2][101];
    int maxV[2];
    int n = strlen(s);
    memset(dp,0,101);
    maxV[0] = maxV[1] = 0;

    maxV[s[0] - '0'] = 1;
    dp[s[0] - '0'][0] = 1;

    for(int i = 1;i<n;i++){
        if(s[i] == s[i-1]){
            dp[s[i] - '0'][i] =  dp[s[i] - '0'][i-1] + 1;
        }
        else{
            dp[s[i] - '0'][i] = 1;
        }

        maxV[0] = max(maxV[0],dp[0][i]);
        maxV[1] = max(maxV[1],dp[1][i]);

    }

    return maxV[1] >  maxV[0];
    
}

（2）寻找数组中心下标

给你一个整数数组 nums ，请计算数组的 中心下标 。

数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。

int pivotIndex(int* nums, int numsSize) {
    
    int sum [10001];
    for(int i = 0;i<numsSize;i++){
        sum[i] = nums[i];
        if(i){
            sum[i] += sum[i-1];
         }
    }

    if(sum[numsSize - 1] == sum[0]){
        return 0;
    }

    for(int i = 1;i<numsSize;i++){
        if(sum[i] == sum[numsSize-1]  - sum[i -1]){
            return i;
        }
    }

    return -1;
}

（3）统计全为1的正方形子矩阵

给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。

示例 1：

输入：matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
输出：15
解释： 
边长为 1 的正方形有 10 个。
边长为 2 的正方形有 4 个。
边长为 3 的正方形有 1 个。
正方形的总数 = 10 + 4 + 1 = 15.

#include <stdio.h>
#include <stdlib.h>

int countSquares(int** matrix, int matrixSize, int* matrixColSize) {
    if (matrix == NULL || matrixSize == 0 || matrixColSize[0] == 0) {
        return 0;
    }
    
    int m = matrixSize;
    int n = matrixColSize[0];
    int** dp = (int**)malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++) {
        dp[i] = (int*)malloc(n * sizeof(int));
    }
    
    int count = 0;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == 1) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = (dp[i - 1][j] < dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1]);
                    dp[i][j] = (dp[i][j] < dp[i - 1][j - 1] ? dp[i][j] : dp[i - 1][j - 1]) + 1;
                }
                count += dp[i][j];
            } else {
                dp[i][j] = 0;
            }
        }
    }
    
    // 释放内存
    for (int i = 0; i < m; i++) {
        free(dp[i]);
    }
    free(dp);
    
    return count;
}

2 二维DP

（1）粉刷房子

假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。

例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。

请计算出粉刷完所有房子最少的花费成本。

int min(int a,int b){
    return a<b?a:b;
}

int minCost(int** costs, int costsSize, int* costsColSize){

    int m = costsColSize[0];
    int n = costsSize;

    int dp[101][3];

    for(int i = 0;i<3;i++){
        dp[0][i] = costs[0][i];
    }

    for(int i = 1;i<n;i++){
        for(int j = 0; j<3;j++){
            dp[i][j] = 1000000000;
            for(int k = 0;k<3;k++){
                if(k != j){
                    dp[i][j] = min(dp[i][j],dp[i-1][k] + costs[i][j]);
                }
            }
        }
    }
    return min(min(dp[n-1][0],dp[n-1][1]),dp[n-1][2]);
}

3 经典DP

[1] 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组：是数组中的一个连续部分。

int max(int a,int b){
    return a>b?a:b;
}

int maxSubArray(int* nums, int numsSize) {

    int dp[100001];
    int maxV = nums[0];
    dp[0] = nums[0];

    for(int i = 1;i<numsSize;i++){

         dp[i] = nums[i];

         if(dp[i-1] > 0){
            dp[i] += dp[i-1];
         }

        maxV = max(maxV,dp[i]);

    }

    return maxV;

}

 [2] 最长单调子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的

子序列

。 

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

int max(int a,int b){
    return a>b?a:b;
}

int lengthOfLIS(int* nums, int numsSize) {

    int maxV = 0;
    int dp[numsSize];

    for(int i = 0;i < numsSize; i++){

        dp[i] = 1;

        for(int j = 0; j < i; ++ j){

            if(nums[j] < nums[i]) {

                if(dp[j] + 1 > dp[i]){

                      dp[i] = dp[j] +1;
                    
                }
            }
        }
        maxV = max(maxV,dp[i]);
    }

  return maxV;
    
}

 （还可以继续使用二分法优化）

（2）最长递增子序列的个数

给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。

注意 这个数列必须是 严格 递增的。

示例 1:

输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

int findNumberOfLIS(int* nums, int numsSize){
    int maxlen=0,ans=0;//maxlen为最长递增子序列长度，ans为其个数
    int dp[numsSize],cnt[numsSize];//dp[i]表示nums中以下标i结尾的最长递增子序列的长度
                                   //cnt[i]表示nums中以下标i结尾的最长递增子序列的个数
    for (int i = 0; i < numsSize; ++i) {
            dp[i] = 1;
            cnt[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (nums[j]<nums[i]) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        cnt[i] = cnt[j]; // dp[i]发生变化,cnt[i]重新计数
                    } else if (dp[j] + 1 == dp[i]) {
                        cnt[i] += cnt[j];//有相同的dp[i]，cnt[i]要再加上cnt[j]
                    }
                }
            }
            if (dp[i] > maxlen) {//先找到最长递增子序列再赋值其个数
                maxlen = dp[i];
                ans = cnt[i]; // 重置计数
            } else if (dp[i] == maxlen) {//如果不同下标最长子序列长度相同再加上其个数
                ans += cnt[i];
            }
        }
        return ans;
}       

 （3）最长等差数列

给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。

回想一下，nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] ，且 0 <= i1 < i2 < ... < ik <= nums.length - 1。并且如果 seq[i+1] - seq[i]( 0 <= i < seq.length - 1) 的值都相同，那么序列 seq 是等差的。

#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))

int longestArithSeqLength(int* nums, int numsSize) {
    int maxVal = nums[0];
    int minVal = nums[0];
    for (int i = 0; i < numsSize; i++) {
        maxVal = MAX(maxVal, nums[i]);
        minVal = MIN(minVal, nums[i]);
    }
    int diff = maxVal - minVal;
    int ans = 1;
    for (int d = -diff; d <= diff; ++d) {
        int f[maxVal + 1];
        memset(f, 0xff, sizeof(f));
        for (int i = 0; i < numsSize; i++) {
            int prev = nums[i] - d; 
            if (prev >= minVal && prev <= maxVal && f[prev] != -1) {
                f[nums[i]] = MAX(f[nums[i]], f[prev] + 1);
                ans = MAX(ans, f[nums[i]]);
            }
            f[nums[i]] = MAX(f[nums[i]], 1);
        }
    }
    return ans;
}

//思路与算法

// 我们可以使用动态规划的方法解决本题。

// 记 f[i][d][num] 表示使用数组 nums 中下标小于等于 i 的元素，构造公差为 d 的等差数列，并且最后一个元素为 num 时，等差数列长度的最大值。在进行状态转移时，我们考虑是否将当前的第 i 个元素作为末项加入等差数列。

// 如果不加入等差数列，那么每一项的答案应该与使用下标小于等于 i−1 的元素对应的答案相同，即：

// f[i][d][num]←f[i−1][d][num]
// 如果加入等差数列，那么有两种情况。第一种是等差数列的长度至少为 2，既然末项是 nums[i]，那么倒数第二项就是 nums[i]−d，这样我们就可以得到状态转移方程：

// f[i][d][nums[i]]←f[i−1][d][nums[i]−d]+1
// 这里需要保证 nums[i]−d 落在满足要求的范围内，即必须在数组 nums 中最小值和最大值之间。并且 f[i−1][d][nums[i]−d] 本身也需要是一个合法的状态，即必须要存在以 nums[i]−d 为末项的等差数组。

// 第二种是等差数列的长度为 1，即 nums[i] 单独形成一个等差数组，即：

// f[i][d][nums[i]]←1
// 由于我们需要求出的是最大值，因此所有的状态转移都会取二者的较大值。如果我们使用数组表示 f，可以将所有状态的初始值均设置为 −1，表示不合法的状态；如果我们使用哈希表表示 f，那么没有在哈希表中出现过的状态，就是不合法的状态。

// 最终的答案即为 f[n−1][..][..] 中的最大值，其中 n 是数组 nums 的长度。

// 需要注意的是，d 的取值范围是 [−diff,diff ]，其中 diff 是数组 nums 中最大值与最小值的差。

// 优化

// 在上面的状态转移方程中，我们发现，当状态的第一维从 i−1 变成 i 后，实际上只有 f[i][d][nums[i]] 可能会相较于 f[i−1][d][nums[i]] 的值发生变化，而其余的值均保持不变。因此，我们可以省去第一维，在状态转移时只需要修改最多一个状态的值。

// 此时，状态变为 f[d][num]，当我们遍历到数组 nums 的第 i 个元素时，只需要进行：

// f[d][nums[i]]←f[d][nums[i]−d]+1
// 以及：

// f[d][nums[i]]←1
// 这两个状态转移即可。进一步我们发现，f[d][..] 只会从 f[d][..] 转移而来，因此我们可以继续省去当前的第一维，使用一个外层循环枚举 d，而在内层循环中，只需要进行：

// f[nums[i]]←f[nums[i]−d]+1(1)
// 以及：

// f[nums[i]]←1
// 这两个状态转移即可。

// 显然，最终的答案至少为 1。因此我们只需要在进行 (1) 的状态转移时，使用 f[nums[i]] 对答案进行更新。

// 作者：力扣官方题解
// 链接：https://leetcode.cn/problems/longest-arithmetic-subsequence/solutions/2238031/zui-chang-deng-chai-shu-lie-by-leetcode-eieq8/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

（4）最长斐波那契数列

如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是 斐波那契式 的：

• n >= 3
• 对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}

给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回  0 。

（回想一下，子序列是从原序列  arr 中派生出来的，它从 arr 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）

示例 1：

输入: arr = [1,2,3,4,5,6,7,8]
输出: 5
解释: 最长的斐波那契式子序列为 [1,2,3,5,8] 。

//（1）
typedef struct {
    int key;
    int val;
    UT_hash_handle hh;
} HashItem;

#define MAX(a, b) ((a) > (b) ? (a) : (b))

int lenLongestFibSubseq(int* arr, int arrSize){
    HashItem *indices = NULL, *pEntry = NULL;
    for (int i = 0; i < arrSize; i++) {
        pEntry = (HashItem *)malloc(sizeof(HashItem));
        pEntry->key = arr[i];
        pEntry->val = i;
        HASH_ADD_INT(indices, key, pEntry);
    }
    int **dp = (int **)malloc(sizeof(int *) * arrSize);
    int ans = 0;
    for (int i = 0; i < arrSize; i++) {
        dp[i] = (int *)malloc(sizeof(int) * arrSize);
        memset(dp[i], 0, sizeof(int) * arrSize);
    }
    for (int i = 0; i < arrSize; i++) {
        for (int j = i - 1; j >= 0 && arr[j] * 2 > arr[i]; j--) {
            int k = -1;
            int target = arr[i] - arr[j];
            pEntry = NULL;
            HASH_FIND_INT(indices, &target, pEntry);
            if (pEntry) {
                k = pEntry->val;
            }
            if (k >= 0) {
                dp[j][i] = MAX(dp[k][j] + 1, 3);
            }
            ans = MAX(ans, dp[j][i]);
        }
    }
    for (int i = 0; i < arrSize; i++) {
        free(dp[i]);
    }
    free(dp);
    HashItem *curr = NULL, *tmp = NULL;
    HASH_ITER(hh, indices, curr, tmp) {
        HASH_DEL(indices, curr);  
        free(curr);         
    }
    return ans;
}

// (2)

int findV(int *arr,int min,int max,int var){
    int idx = 0;
    while(min <= max){
        int mid = (min+max)/2;
        if(var >arr[mid]){
            min = mid + 1;
        }else if(var < arr[mid]){
            max = mid - 1;
        }
        else{
            return mid;
        }
    }
    return -1;
}

int max(int a,int b){return a>b?a:b;}

int lenLongestFibSubseq(int* arr, int arrSize){

    int ans = 0;
    int dp[1001][1001];
    for(int i= 0;i<arrSize;i++){
        for(int j= i+1;j<arrSize;j++){
            int idx = findV(arr,0,i-1,arr[j]-arr[i]);
            if(idx != -1){
                dp[i][j] = dp[idx][i] + 1;
            }
            else{
                dp[i][j] = 2;
            }
            ans = max(ans,dp[i][j]);
        }
    }

    return ans>=3?ans:0;

}

[3] 最长公共子序列

（1）最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

• 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

int max(int a,int b){return a>b?a:b;}

int longestCommonSubsequence(char * text1, char * text2){
   int ans = 0;
   int dp[1001][1001];
   int n = strlen(text1);
   int m = strlen(text2);

   for(int i = 0;i<n;i++){
     for(int j = 0;j<m;j++){
       int same = (text1[i] == text2[j]?1:0);
        if(i == 0 && j == 0){
            dp[i][j] = same;
        }else if(i == 0){
            dp[i][j] = dp[i][j-1] || same;
        }else if(j == 0){
            dp[i][j] = dp[i-1][j] || same;
        }else if(same){
            dp[i][j] = dp[i-1][j-1] + 1; 
        }else{
            dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
        }
     }
   }
   return dp[n-1][m-1];
}

（2）最长回文子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

• 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

int max(int a,int b){return a>b?a:b;}

int longestCommonSubsequence(char * text1, char * text2){
   int ans = 0;
   int dp[1001][1001];
   int n = strlen(text1);
   int m = strlen(text2);

   for(int i = 0;i<n;i++){
     for(int j = 0;j<m;j++){
       int same = (text1[i] == text2[j]?1:0);
        if(i == 0 && j == 0){
            dp[i][j] = same;
        }else if(i == 0){
            dp[i][j] = dp[i][j-1] || same;
        }else if(j == 0){
            dp[i][j] = dp[i-1][j] || same;
        }else if(same){
            dp[i][j] = dp[i-1][j-1] + 1; 
        }else{
            dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
        }
     }
   }
   return dp[n-1][m-1];
}

[4] 最短编辑距离

（1）编辑距离 （困难）

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。

你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.length();
        int m = word2.length();

        // 有一个字符串为空串
        if (n * m == 0) return n + m;

        // DP 数组
        vector<vector<int>> D(n + 1, vector<int>(m + 1));

        // 边界状态初始化
        for (int i = 0; i < n + 1; i++) {
            D[i][0] = i;
        }
        for (int j = 0; j < m + 1; j++) {
            D[0][j] = j;
        }

        // 计算所有 DP 值
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                int left = D[i - 1][j] + 1;
                int down = D[i][j - 1] + 1;
                int left_down = D[i - 1][j - 1];
                if (word1[i - 1] != word2[j - 1]) left_down += 1;
                D[i][j] = min(left, min(down, left_down));

            }
        }
        return D[n][m];
    }
};

[5] 杨辉三角

（1）杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

int** generate(int numRows, int* returnSize, int** returnColumnSizes) {
    // 设置返回的行数
    *returnSize = numRows;

    // 分配存储每行列数的数组
    *returnColumnSizes = (int*)malloc(numRows * sizeof(int));

    // 分配存储杨辉三角的二维数组
    int** triangle = (int**)malloc(numRows * sizeof(int*));

    for (int i = 0; i < numRows; i++) {
        // 设置当前行的列数
        (*returnColumnSizes)[i] = i + 1;

        // 为当前行分配内存
        triangle[i] = (int*)malloc((i + 1) * sizeof(int));

        for (int j = 0; j <= i; j++) {
            if (j == 0 || j == i) {
                // 每行的第一个和最后一个元素为 1
                triangle[i][j] = 1;
            } else {
                // 其他元素为上一行相邻两个元素之和
                triangle[i][j] = triangle[i - 1][j] + triangle[i - 1][j - 1];
            }
        }
    }

    return triangle;
}

（2）不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7
输出：28

 旋转45度 就得到一个杨辉三角

int uniquePaths(int m, int n){
    int ans = 0;
    int dp[1024][1024];
    for(int i = 1;i <= m;i ++){
        for(int j = 1;j <= n;j++){
            if(j == 1 || j == 1){
                dp[i][j] = 1;
            }else{
                dp[i][j] = dp[i][j-1] + dp[i-1][j];
            }
        }
    }
    return dp[m][n];
}

（3）珠宝的最高价值

现有一个记作二维矩阵 frame 的珠宝架，其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为：

• 只能从架子的左上角开始拿珠宝
• 每次可以移动到右侧或下侧的相邻位置
• 到达珠宝架子的右下角时，停止拿取

注意：珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝，比如 frame = [[0]]。

示例 1：

输入：frame = [[1,3,1],[1,5,1],[4,2,1]]
输出：12
解释：路径 1→3→5→2→1 可以拿到最高价值的珠宝

int max(int a,int b){
    return a>b?a:b;
}

int jewelleryValue(int** frame, int frameSize, int* frameColSize) {

    int dp[201][201];
    
    for(int i = 0;i < frameSize;i++){
        for(int j = 0;j < frameColSize[i];j ++){
            if(i == 0 && j== 0){
                dp[i][j] = frame[0][0];
            }else if(i == 0){
                dp[i][j] = frame[i][j] + dp[i][j-1];
            }else if(j == 0){
                dp[i][j] = frame[i][j] + dp[i-1][j];
            }else{
                dp[i][j] = frame[i][j] + max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
 
    return dp[frameSize - 1][frameColSize[frameSize - 1] - 1];
    
}

（4）最小路径之和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：一个机器人每次只能向下或者向右移动一步。

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

int min(int a,int b){
    return a<b?a:b;
}

int minPathSum(int** grid, int gridSize, int* gridColSize){

 int dp[201][201];
    
    for(int i = 0;i < gridSize;i++){
        for(int j = 0;j < gridColSize[i];j ++){
            if(i == 0 && j== 0){
                dp[i][j] = grid[0][0];
            }else if(i == 0){
                dp[i][j] = grid[i][j] + dp[i][j-1];
            }else if(j == 0){
                dp[i][j] = grid[i][j] + dp[i-1][j];
            }else{
                dp[i][j] = grid[i][j] + min(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
 
    return dp[gridSize - 1][gridColSize[gridSize - 1] - 1];

}

[6]  经典股票问题

（1）买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

int min(int a,int b){
    return a<b?a:b;
}

int max(int a,int b){
    return a>b?a:b;
}


int maxProfit(int* prices, int pricesSize) {

    int* dp = (int *)malloc(sizeof(int) * pricesSize);
    int maxV = 0;

    for(int i = 0;i < pricesSize;i++){

        if(i == 0){
            dp[i] = prices[0];
        }
        else{
            dp[i] = min(prices[i],dp[i-1]);
        }

        maxV = max(maxV,(prices[i] - dp[i]));
        
    }

    return maxV;
}

 （2）买卖股票的最佳时机Ⅱ

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

示例 1：

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。
最大总利润为 4 + 3 = 7 。

int max(int a,int b){
    return a>b?a:b;
}

int maxProfit(int* prices, int pricesSize) {
    int maxM =  10000000;
    int minM = -10000000;
    int dp[pricesSize][4];
    // dp[i][0]  未买入
    // dp[i][1]  买入
    // dp[i][2]  持有中
    // dp[i][3]  卖出

    for(int i = 0;i< pricesSize; i++){

        if(i == 0){
            dp[i][0] = 0;
            dp[i][1] = -prices[i];
            dp[i][2] = minM;
            dp[i][3] = minM;
        }
        else{
            dp[i][0] = max(dp[i-1][3],dp[i-1][0]);
            dp[i][1] = max(dp[i-1][3],dp[i-1][0]) - prices[i];
            dp[i][2] = max(dp[i-1][2],dp[i-1][1]);
            dp[i][3] = max(dp[i-1][1],dp[i-1][2]) + prices[i];
        }
    }

    return max(dp[pricesSize-1][0],max(dp[pricesSize -1][1],max(dp[pricesSize-1][2],dp[pricesSize-1][3])));

}

 （3）买卖股票的最佳时机Ⅲ

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

#define max(a, b) ((a) < (b) ? (b) : (a))

int maxProfit(int* prices, int pricesSize) {
    int buy1 = -prices[0], sell1 = 0;
    int buy2 = -prices[0], sell2 = 0;
    for (int i = 1; i < pricesSize; ++i) {
        buy1 = max(buy1, -prices[i]);
        sell1 = max(sell1, buy1 + prices[i]);
        buy2 = max(buy2, sell1 - prices[i]);
        sell2 = max(sell2, buy2 + prices[i]);
    }
    return sell2;
}

  （4）买卖股票的最佳时机Ⅳ

给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1：

输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

int maxProfit(int k, int* prices, int pricesSize) {
    int n = pricesSize;
    if (n == 0) {
        return 0;
    }

    k = fmin(k, n / 2);
    int buy[n][k + 1], sell[n][k + 1];
    memset(buy, 0, sizeof(buy));
    memset(sell, 0, sizeof(sell));

    buy[0][0] = -prices[0];
    sell[0][0] = 0;
    for (int i = 1; i <= k; ++i) {
        buy[0][i] = sell[0][i] = INT_MIN / 2;
    }

    for (int i = 1; i < n; ++i) {
        buy[i][0] = fmax(buy[i - 1][0], sell[i - 1][0] - prices[i]);
        for (int j = 1; j <= k; ++j) {
            buy[i][j] = fmax(buy[i - 1][j], sell[i - 1][j] - prices[i]);
            sell[i][j] = fmax(sell[i - 1][j], buy[i - 1][j - 1] + prices[i]);
        }
    }
    int ret = 0;
    for (int i = 0; i <= k; i++) {
        ret = fmax(ret, sell[n - 1][i]);
    }

    return ret;
}

4 背包DP

[1] 零一背包

（1）分割等和子集

给定一个非空的正整数数组 nums ，请判断能否将这些数字分成元素和相等的两部分。

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：nums 可以分割成 [1, 5, 5] 和 [11] 。

bool canPartition(int* nums, int numsSize){

    int sum = 0;
    int dp[200001];
    for(int i = 0;i<numsSize;i++){
        sum += nums[i];
    }

    memset(dp,0,sizeof(dp));

    if(sum & 1){return false;}

    sum /= 2;
    dp[0] = 1;

    for(int i = 0;i<numsSize;i++){
       for(int j = sum;j >= nums[i];j--){
            dp[j] |= dp[j - nums[i]];
       }
       if(dp[sum]) return true;
    }
    return false;
}

[2] 完全背包

（1）最少的硬币数量

给定不同面额的硬币 coins 和一个总金额 amount 。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。

class Solution {
    //define maxn 10010
    //define inf 10000000
    int dp[maxn];
public:
    int coinChange(vector<int>& coins, int amount) {
        int i, j;
        for(i = 0; i <= amount; ++i) {
            dp[i] = inf;
        }
        dp[0] = 0;
        for(i = 0; i < coins.size(); ++i) {
            for(j = coins[i]; j <= amount; ++j) {
                if( dp[j-coins[i]] + 1 < dp[j]) {
                    dp[j] = dp[j-coins[i]] + 1;
                }
            }
        }
        if(dp[amount] >= inf) dp[amount] = -1;
        return dp[amount];
    }
};

5 记忆化搜索

（1）最长递增路径

给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。

示例 1：

输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出：4 
解释：最长递增路径为 [1, 2, 6, 9]。

int max(int a,int b){
    return a>b?a:b;
}

int dir[4][2] = {
  
  {0,1},{0,-1},{1,0},{-1.,0}};

int dfs(int dp[2010][2010],int** matrix, int matrixSize, int* matrixColSize,int x,int y){

    int tx,ty;

    if(dp[x][y] != -1){
        return dp[x][y];
    }

    dp[x][y] = 1;
    for(int i = 0;i < 4;i++){
        tx = x + dir[i][1];
        ty = y + dir[i][0];

        if(tx < 0 || ty < 0 || tx >= matrixSize || ty >= matrixColSize[tx]){
            continue;
        }

        if(matrix[tx][ty] >= matrix[x][y]){
            continue;
        }

        dp[x][y] = max(dp[x][y],dfs(dp,matrix,matrixSize,matrixColSize,tx,ty)+1);
    }

    return dp[x][y];

}

int longestIncreasingPath(int** matrix, int matrixSize, int* matrixColSize){
    int length = 1;
    int dp[2010][2010];

    memset(dp,-1,sizeof(dp));

    for(int i = 0;i<matrixSize;i++){
        for(int j = 0;j<matrixColSize[i];j++){
            length = max(length,dfs(dp,matrix,matrixSize,matrixColSize,i,j));
        }
    }

    return length;
}

学习时间 2025.2.2 

关于动态规划学习 这份笔记并不完善 还有部分题型没有分类学习 后续有涉及再继续补充