int findLengthOfLCIS(vector& nums) {
        int result=1;
        //dp表示下标为i时最大连续递增的个数
        int dp[nums.size()+1];
        for(int i=0;inums[i-1]){
                dp[i]= dp[i-1]+1;
            }
            result=max(result,dp[i]);
        }

        
    return result;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

m[i][j]=min(m[i][k]+m[k+1][j]+p[i-1]p[k][j]):自身之和加上乘积数的总数
其中i,j是 从哪个矩阵到到哪个矩阵 k是切片 目的是找到i到j的最小子序列 p是列数矩阵相乘得到的乘积次数 比如A1,A2,A3 ×A5  i就是A矩阵的二行数 A3矩阵的列数 A5矩阵的列数.
1
2

#include
using namespace std;
#define Maxn 100000
int m[Maxn][Maxn]; //表示i到j矩阵连城的最优值
int p[Maxn]; //p表示第i个矩阵的列数
void Maxi(int n){
    //初始化因为自己×自己为0赋值0
    for(int i=0;i<=n;i++){
        m[i][i]=0;
    }
    //len表示矩阵的长度 遍历每一个长度的矩阵 从2个到n个长度矩阵
    for(int len=2;len<=n;len++){
        //枚举每一个长度矩阵 记录起点坐标比如 1,2  2,3  4,5
        for(int i=1;i<=n-len+1;i++){
            //记录终点 
            int j=i+len-1;
            //记录 i到j矩阵的最优值 先从自身去分割然后在遍历所有
            //比如  m[1,1]+m[2,5]+P0P1P5,
            m[i][j]= m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j];
            //然后遍历剩下切分位置
            for(int cut=i+1;i

• 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
• 33
• 34
• 35

学习参考

https://www.bilibili.com/video/BV1U54y1D7sJ?share_source=copy_web&vd_source=88f5a5f5ee6323ab3447f683ec7e1e7a
1

剑指 Offer II 095. 最长公共子序列

对于字符串s1, s2 从后往前看 当第i,j个位置,i指s1遍历位置 j指s2遍历位置

dp[i][j]=?
情况1：如果字符串相同发生匹配时,则是上一个匹配点即是i-1 j-1的最大长度+1
情况2:如果字符串匹配位置不相同时:则是 s1上一个匹配位置 与s2上一个匹配位置的最大值
得到递推关系
if(s[i]==[sj]):
	dp[i][j]=dp[i-1][j-1]+1
else{
	dp[i][j]=max(dp[i-1][j],dp[i][j-1])
}
1
2
3
4
5
6
7
8
9

代码为

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int a=text1.length();
        int b=text2.length();
        int dp[a+1][b+1];//dp表示 1和2下标的最长子序列
        for(int i=0;i<=text1.size();i++){
            for(int j=0;j<=text2.size();j++){
                //初始化都为空串时长度为0
                dp[i][j]=0;
            }
        }
        for(int i=1;i<=text1.size();i++){
            for(int j=1;j<=text2.size();j++){
                if(text1[i-1]==text2[j-1])
                    dp[i][j]= dp[i-1][j-1]+1;
                else
                    dp[i][j]= max(dp[i-1][j],dp[i][j-1]);
               
            }
        }
        return dp[a][b];
        

    }
};
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

背包

推导公式

dp[j]:表示背包重量为j时所能背的最大价值

dp由两个维度推出

第一个:放入i物品 所产生的最大价值

第二个:不放i物品所产生的最大价值

所以dp[j]=max(dp[j],dp[j-weight[i]]+value[i])

遍历顺序

首先看重量

如果时正序: 以这个为为例 dp[1]=dp[1-1]+15=15  ,dp[2]=dp[2-1]+15=30 表示物品0被重复放入了 所以遍历背包重量时候一定要倒叙.

1
2

再来看先遍历物品还是背包重量

如果是先遍历背包重量 由于在遍历过程中 不能被重复放入只能放入一个物品 显然不合适

所以是先物品后重量
1
2
3

    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
1
2
3
4
5

完全背包

所以对应的是完全背包

每件物品都有无限个（也就是可以放入背包多次

那末不久正好对应重复放入的情况 只需要正序遍历即可

而这里先背包和先物品顺序就无所谓了 因为先背包重量的话由于是正序 再次之前已经放入物品了有了其价值
1

int main(){
    int weight[3]={1,3,4};
    int value[3]= {10,20,30};
    int bagweight=4;
    //遍历物品
    for(int i=0;i<3;i++){
        //遍历背包
        for(int j=weight[i];j<=bagweight;j++){
            dp[j]= max(dp[j],dp[j-weight[i]]+value[i]);
            
        }
    }




    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

[3]= {10,20,30};
int bagweight=4;
//遍历物品
for(int i=0;i<3;i++){
//遍历背包
for(int j=weight[i];j<=bagweight;j++){
dp[j]= max(dp[j],dp[j-weight[i]]+value[i]);

    }
}




return 0;
1
2
3
4
5
6
7

}

1