088. 爬楼梯的最少成本

class Solution {

public:

    int minCostClimbingStairs(vector<int>& cost) {

        int n=cost.size();

        vector<int>f(n+1);

        f[0]=cost[0],f[1]=cost[1];

        //走到第i级台阶 最小代价

        //状态转移 从前一个或 前两个走上来

        cost.push_back(0);

        for(int i=2;i<=n;i++)

        {

            f[i]=cost[i]+min(f[i-1],f[i-2]);

        }

        return f[n];

    }

};

089. 房屋偷盗

class Solution {

public:

       /*

            f[i][0]

            f[i][1]

               偷还是不偷

            */

 int rob(vector<int>& nums) {

        int n=nums.size();

        vector<vector<int>>f(n+1,vector<int>(2));

        f[1][1]=nums[0];

        for(int i=2;i<=n;i++)

        {

            f[i][0]=max(f[i-1][0],f[i-1][1]);//没偷前一个咋样都无所谓

            f[i][1]=max(f[i-1][0],f[i-2][1]+nums[i-1]);

        }

        return max(f[n][0],f[n][1]);

    }

};

090. 环形房屋偷盗

就两种情况 选1还是不选1

class Solution {

public:

       /*

            f[i][0]

            f[i][1]

               偷还是不偷

            */

 int rob(vector<int>& nums) {

        int n=nums.size();

        if(n==1)return nums[0];

        vector<vector<int>>f(n+1,vector<int>(2));

      //不选1 不初始化f[1][1]

        for(int i=2;i<=n;i++)

        {

            f[i][0]=max(f[i-1][0],f[i-1][1]);//没偷前一个咋样都无所谓

            f[i][1]=f[i-1][0]+nums[i-1];

        }

         int ans= max(f[n][0],f[n][1]);

         f[1][1]=nums[0];

          for(int i=2;i<=n;i++)

        {

            f[i][0]=max(f[i-1][0],f[i-1][1]);//没偷前一个咋样都无所谓

            f[i][1]=f[i-1][0]+nums[i-1];

        }

        ans=max(ans,f[n][0]);//选了1就别选n

        return ans;

    }

};

091. 粉刷房子

class Solution {

public:

/*

f[i][j]

j是颜色 从另外两个转移

*/

    int minCost(vector<vector<int>>& cost) {

        int n=cost.size();

        vector<vector<int>>f(n,vector<int>(3));

        f[0][0]=cost[0][0],f[0][1]=cost[0][1],f[0][2]=cost[0][2];

        for(int i=1;i<n;i++)

        {

            f[i][0]=cost[i][0]+min(f[i-1][1],f[i-1][2]);

             f[i][1]=cost[i][1]+min(f[i-1][0],f[i-1][2]);

              f[i][2]=cost[i][2]+min(f[i-1][1],f[i-1][0]);

        }

        return min(min(f[n-1][0],f[n-1][1]),f[n-1][2]);

    }

};

092. 翻转字符

前缀和

class Solution {

public:

/*

f[i] 1的前缀和

2e4

*/

    int minFlipsMonoIncr(string s) {

        int n=s.size();

        vector<int>f(n+1);

        for(int i=1;i<=n;i++)

        {

            f[i]=f[i-1]+ (s[i-1]=='1');

        //    cout<<f[i];

        }

        //puts("");

        int ans=min(f[n],n-f[n]);//全0 全1

         for(int i=1;i<=n;i++)

         {

             //把 i及以前变为0 以后变为1的代价 01111  00001

             int res=f[i]-f[1-1];//1~i的1变为0

             res+=(n-i)-(f[n]-f[i+1-1]);//i+1~n中0的个数;

          //   cout<<res<<endl;

             ans=min(ans,res);

         }

        return ans;

    }

};

093. 最长斐波那契数列

class Solution {

public:

/*

状态表示

f[i][j] 以arr[i]为结尾 arr[j]为arr[i]前一个元素组成的数列 的 最大值

状态转移

从f[j][k]

*/

    int lenLongestFibSubseq(vector<int>& arr) {

        int n=arr.size();

        vector<vector<int> >f(n+1,vector<int>(n+1));

        int res=0;

        unordered_map<int,int>pos;

        for(int i=0;i<n;i++)

        {

            pos[arr[i]]=i;//记录地址

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

            {

                f[i][j]=2;

                //找 j前面有没有x=arr[i]-arr[j]

                int x=arr[i]-arr[j];

                if(x<arr[j]&&pos.count(x)){

                    int k=pos[x];

                    f[i][j]=max(f[i][j],f[j][k]+1);

                }

                res=max(res,f[i][j]);

            }

        }

        return res<3?0:res;

    }

};

洞94 ?!最少回文分割 hard

class Solution {

public:

/*

f[i]状态表示  从1~i的方案  属性：最小值

阶段划分

可以分为1~i 2~i ... i~i

假设最后一步k~i转移

(1... k-1)  (k...i)

转移方程

f[i]=min(f[i],f[k-1]+1);

快速枚举i 到j是不是回文串 g[i][j]

1.s[i]==s[j]

2. j-i== 0、1 || g[i+1][j-1]

*/

    int minCut(string s) {

        int n=s.size();

        s=' '+s;//单引号 方便 下标从1开始

        vector<int>f(n+1,1e9);

        vector<vector<bool>>g(n+1,vector<bool>(n+1));

        //初始化 st  第一次dp

        // i到j j先循环 保证g[i+1][j-1]先创建出来了

        for(int j=1;j<=n;j++)

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

            if(s[i]==s[j]){

                if(j-i<2||g[i+1][j-1])g[i][j]=true;

            }

        }

        f[0]=0;//0种方案

        for(int i=1;i<=n;i++)

        for(int j=1;j<=i;j++){//j==i 1~(i-1) i

        if(g[j][i]){//j前 i后

           f[i]=min(f[i],f[j-1]+1);

        }

        }

        return f[n]-1;

     }

};

095. 最长公共子序列

模板题 背过 不解释

class Solution {

public:

/*

状态表示

f[i][j] a 1~i

        b 1~j

属性 max

阶段划分

两个字符串的位置（已处理的前缀长度）

*/

    int longestCommonSubsequence(string s1, string s2) {

        int n=s1.size(),m=s2.size();

        s1=' '+s1;s2=' '+s2;

        vector<vector<int>>f(n+1,vector<int>(m+1,0));

        f[n][0]=f[0][m]=0;

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

            for(int j=1;j<=m;j++){

                f[i][j]=max(f[i-1][j],f[i][j-1]);

                if(s1[i]==s2[j])f[i][j]=max(f[i-1][j-1]+1,f[i][j]);

            }

        }

        return f[n][m];

    }

};

老美从来没看过的洞96?！字符串交织

class Solution {

public:

/*

f[i][j]

a 1~i

b 1~j 能组成c 1~i+j 

属性bool

阶段划分

i-1 j

i j-1 能组成1~i+j-1

转移方程

if(a[i]==c[i+j])f[i][j]|=f[i-1][j]

if(b[j]==c[i+j])f[i][j]|=f[i][j-1]

f[0][0]=true;

*/

    bool isInterleave(string a, string b, string c) {

        int n=a.size(),m=b.size();

        if(n+m!=c.size())return false;

        a=' '+a;b=' '+b;c=' '+c;

        vector<vector<bool>>f(n+1,vector<bool>(m+1));

        f[0][0]=true;

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

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

                if(i&&a[i]==c[i+j])f[i][j]=f[i][j]||f[i-1][j];

                if(j&&b[j]==c[i+j])f[i][j]=f[i][j]||f[i][j-1];

               // cout<<f[i][j];

            }

        }

        return f[n][m];

    }

};

097. 子序列的数目 （多想想，不太熟）

  //  typedef long long LL;

class Solution {

public:

/*

f[i][j]状态表示s 1~i 组成 t 1~j的方案数

属性cnt

状态划分

if(s[i]!=t[j]) i不能与j匹配 所以f[i][j]=f[i-1][j]

i既可以与j匹配 也可以不与j匹配f[i][j]=f[i-1][j-1]+f[i-1][j]

f[1~n][0]=1;

*/

    int numDistinct(string s, string t) {

        int n=s.size(),m=t.size();

        s=' '+s;t=' '+t;

        vector<vector<unsigned long long>>f(n+1,vector<unsigned long long >(m+1,0));

         for(int i=0;i<=n;i++)f[i][0]=1;//因为s可以从不同下标匹配

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

            for(int j=1;j<=m;j++){

                f[i][j]=f[i-1][j];

                if(s[i]==t[j])

                   f[i][j]+=f[i-1][j-1];

            }

        }

        return f[n][m];

    }

};

098. 路径的数目

class Solution {

public:

    int uniquePaths(int n, int m) {

        vector<vector<int>>f(n+1,vector<int>(m+1));

        f[1][1]=1;

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

            for(int j=1;j<=m;j++){

                if(i>1)f[i][j]+=f[i-1][j];

                if(j>1)f[i][j]+=f[i][j-1];

            }

        }

        return f[n][m];

    }

};

099. 最小路径之和

class Solution {

public:

/*

到i,j这个点 最小代价

f[i][j]

i>2f[i-1][j]

f[i][j-1]

*/

    int minPathSum(vector<vector<int>>& grid) {

        int n=grid.size(),m=grid[0].size();

        vector<vector<int>>f(n+1,vector<int>(m+1,1e9));

       f[1][1]=grid[0][0];

        //要初始化正无穷

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

            for(int j=1;j<=m;j++){

                if(j>1)f[i][j]=min(f[i][j],f[i][j-1]);

                if(i>1)f[i][j]=min(f[i][j],+f[i-1][j]);

                if(i>1||j>1)f[i][j]+=grid[i-1][j-1];

            }

        }

        return f[n][m];

    }

};

100. 三角形中最小路径之和

class Solution {

public:

/*

1

12

123

1234只能从上方或者斜上方转移

*/

    int minimumTotal(vector<vector<int>>& triangle) {

        int n=triangle.size(),m=triangle[n-1].size();

        vector<vector<int>>f(n+1,vector<int>(m+1,1e9));

        //初始化正无穷

        f[1][1]=triangle[0][0];

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

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

                if(i>1||j>1)f[i][j]=f[i-1][j];//除了1，1都能从上方转移

                //从斜上方转移的条件是j>=2

                if(j>1)f[i][j]=min(f[i][j],f[i-1][j-1]);

                if(i>1||j>1)f[i][j]+=triangle[i-1][j-1];

            }

        }

        int res=2e9;

        for(int i=1;i<=m;i++)res=min(res,f[n][i]);

        return res;

    }

};

101. 分割等和子集

class Solution {

public:

/*

01背包

f[i][j] 前i个选 能不能拼成j这个数

属性 bool

状态划分

选与不选

f[i-1][j]

f[i-1][j-x] j>=x x为nums元素

*/

    bool canPartition(vector<int>& nums) {

        int m=0;

        for(auto x:nums)m+=x;

        if(m%2)return false;

        int n=nums.size();

        vector<vector<int>>f(n+1,vector<int>(m+1));

        m/=2;

        //cout<<m<<endl;

       f[0][0]=1;

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

           //  f[i][0]=1;

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

                f[i][j]=f[i-1][j];//不选i

                 int x=nums[i-1];

                if(j>=x)f[i][j]|=f[i-1][j-x];//选i

                //cout<<i<<"."<<j<<" "<<f[i][j]<<endl;

            }

        }

        return f[n][m];

    }

 bool canPartition(vector<int>& nums) {

        int m=0;

        for(auto x:nums)m+=x;

        if(m%2)return false;

        m/=2;

         vector<int>f(m+1);

       f[0]=1;

        for(int x:nums){

            for(int j=m;j>=x;j--)f[j]|=f[j-x];

        }

        return f[m];

    }

};

102. 加减的目标值

class Solution {

public:

/*

状态表示

f[i][j] 前i个全选 总和为j的方案数

为什么全选？

不全选没意义啊 你知道前i个选其中几个 总和为j有什么用？题目用不了

属性cnt

状态划分

选前i-1个  总和为j-x j+x的方案数

f[i-1][j-x]

f[i-1][j+x]

注意0 <= sum(nums[i]) <= 1000

审题很重要 我本以为要offset 2e5

-1000~1000 -> 0~2000

*/

    int findTargetSumWays(vector<int>& nums, int target) {

        if(target<-1000||target>1000)return 0;

        int offset=1000,n=nums.size();

        vector<vector<int>>f(n+1,vector<int>(2001));

        f[0][offset]=1;

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

            int x=nums[i-1];

            for(int j=-1000;j<=1000;j++){

                if(j-x>=-1000)f[i][j+offset]+=f[i-1][j-x+offset];

                if(j+x<=1000)f[i][j+offset]+=f[i-1][j+x+offset];

            }

        }

        return f[n][target+offset];

    }

};

103. 最少的硬币数目

class Solution {

public:

/*

表示

f[j] 前i个货币选 总金额为j最少需要多少个硬币

属性min

划分

 f[i-1][j]

 f[i-1][j-x]+1

 完全背包问题 正向枚举

 0块钱只需要0个硬币 f[0]=0

*/

    int coinChange(vector<int>& coins, int m) {

        vector<int>f(m+1,1e9);

        f[0]=0;

        for(int x:coins){

            for(int j=x;j<=m;j++){

                     f[j]=min(f[j],f[j-x]+1);

            }

        }

        return f[m]==1e9?-1:f[m];

    }

};

104. 排列的数目 （没想明白）

class Solution {

public:

/*

这题不是完全背包会将 所有排列方案当成一种

为什么先枚举j没想明白

*/

    int combinationSum4(vector<int>& nums, int m) {

        vector<long long >f(m+1,0);

        f[0]=1;

     for(int j=1;j<=m;j++)

     for(int x:nums){

         if(j>=x)f[j]=(f[j]+f[j-x])%INT_MAX;

     }

        return f[m];

    }

};

最新文章

1. 实验：Oracle直接拷贝物理存储文件迁移
2. MySQL服务 - MySQL程序的配置文件、参数、变量查看
3. .NET开发 正则表达式中的 Bug
4. java.sql.SQLException: null, message from server: “Host ‘xxx’ is not allowed to connect
5. ButterKnife View 注入
6. h.264 scanning process for transform coefficients
7. HDOJ_就这么个烂题总是WA先放这把
8. usaco training 4.2.4 Cowcycles 题解
9. matlab读取图片的异常表现
10. installation failed with message INSTALL_FAILED_INSUFFICIENT_STORG
11. hMailServer相关视频教程
12. JavaWeb三大组件之Filter
13. Akka-CQRS（3）- 再想多点，全面点
14. sqlmap-学习1 配置环境
15. BZOJ.1492.[NOI2007]货币兑换(DP 斜率优化 CDQ分治/Splay)
16. crm --- 1.admin , 展示列表 和 分页
17. python--第十一天总结（paramiko 及数据库操作）
18. 怎样用CMD命令强行删除文件?
19. [Python] 震惊, 我居然用Python干这种事ꈍ .̮ ꈍ
20. PySide图形界面开发（一）

热门文章

1. js 全屏代码实现方法
2. ECharts 提示框组件Tooltip属性大全（包含文本注释）
3. JZOJ 4318. 【NOIP2015模拟11.5】俄罗斯套娃
4. 使用flex布局（多行，一行三个），换行后最后一行左右对齐问题
5. Ansible介绍以及基于角色搭建LNMP和zabbix
6. XView 架构升级之路
7. JAVA排序的方法
8. unity resMgr
9. Python爬虫-爬取17K小说
10. mybatis动态标签——choose、when、otherwise