• 牛客竞赛每日俩题 - 动态规划1

    目录

    DP入门（存储之前状态以简化）

    DP解决最短路问题

    DP入门（存储之前状态以简化）

    拆分词句_牛客题霸_牛客网

     思路：

    方法：动态规划
    状态：
            子状态：前1 ， 2 ， 3 ， ...,n 个字符能否根据词典中的词被成功分词
            F(i): 前 i 个字符能否根据词典中的词被成功分词
    状态递推：
            F(i): true{j } OR false
            在j 小于 i 中，只要能找到一个 F(j) 为 true ，并且从 j+1 到 i 之间的字符能在词典
            中找到，则F(i) 为 true
    初始值：
            对于初始值无法确定的，可以引入一个不代表实际意义的空状态，作为状态的起始
            空状态的值需要保证状态递推可以正确且顺利的进行，到底取什么值可以通过简单
            的例子进行验证
            F(0) = true
    返回结果： F(n)

    例如题目样例：

    当i==3时 有F[0]==true&&可找到[0,3]中有now，所以canbreak[3]==true;

    当i==7时 有F[3]==true&&可找到[3,7]有code，所以canbreak[7]==true;

    总结：利用F[i]存之前的状态是否可分割，然后搜索后面有无字符，两者都为true则这个整体可分割

    1. class Solution {
    2. public:
    3.     bool wordBreak(string s, unordered_set &dict) {
    4.         if(s.empty()) return false;
    5.         if(dict.empty()) return false;
    6.  
    7.         vector<bool> canbreak(s.size()+1,false);
    8.         canbreak[0]=true;
    9.  
    10.         for(int i=1;i<=s.size();i++)
    11.             for(int j=i-1;j>=0;j--){
    12.                 if(canbreak[j]&&dict.find(s.substr(j,i-j))!=dict.end()){
    13.                     // F(i): true{j 
    14.                     canbreak[i]=true; 
    15.                     break;
    16.                 }
    17.                     
    18.             }
    19.             return canbreak[s.size()];
    20.     }
    21. };

    DP解决最短路问题

    三角形_牛客题霸_牛客网

    状态：
            子状态：从(0,0) 到 (1,0),(1,1),(2,0),...(n,n) 的最短路径和
            F(i,j): 从 (0,0) 到 (i,j) 的最短路径和
    状态递推：
            F(i,j) = min( F(i-1, j-1), F(i-1, j)) + triangle[i][j]
    初始值：
            F(0,0) = triangle[0][0]
    返回结果：
            min(F(n-1, i))

     方法一：递推法

    利用dp算出所有路径，再找最短值

    1. class Solution {
    2. public:
    3.     int minimumTotal(vectorint> > &triangle) {
    4.         if(triangle.empty()) return 0;
    5.  
    6.         vectorint>> minsum(triangle);
    7.         int line=triangle.size();
    8.  
    9.         for(int i=1;i
    10.             for(int j=0;j<=i;j++){
    11.                 //处理左右边界
    12.                 if(j==0) minsum[i][j]=minsum[i-1][j]+triangle[i][j];
    13.                 else if(j==i) minsum[i][j]=minsum[i-1][j-1]+triangle[i][j];
    14.                 else{//核心操作
    15.                     minsum[i][j]=min(minsum[i-1][j],minsum[i-1][j-1])+triangle[i][j];
    16.                 }
    17.             }
    18.         }
    19.         int res=minsum[line-1][0];//找到最后一行的最短步数
    20.         for(int i=1;imin(res,minsum[line-1][i]);
    21.         return res;
    22.     }
    23. };

    方法二：逆推法

    状态：
    子状态：
            从(n,n),(n,n-1),...(1,0),(1,1),(0,0) 到最后一行的最短路径和
            F(i,j): 从 (i,j)到最后一行的最短路径和
    状态递推：
            F(i,j) = min( F(i+1, j), F(i+1, j+1)) + triangle[i][j]
    初始值：
            F(n-1,0) = triangle[n-1][0], F(n-1,1) = triangle[n-1][1],..., F(n-1,n-1) = triangle[n-1] [n-1]
    返回结果：
            F(0, 0) 
    1. class Solution {
    2. public:
    3.     int minimumTotal(vectorint> > &triangle) {
    4.         if(triangle.empty()) return 0;
    5.  
    6.         vectorint>> minsum(triangle);
    7.         int line=triangle.size();
    8.  
    9.         // 从倒数第二行开始
    10.         for(int i=line-2;i>=0;i--)
    11.         {
    12.             for(int j=0;j<=i;j++){
    13.                 minsum[i][j]=min(minsum[i+1][j],minsum[i+1][j+1])+triangle[i][j];
    14.             }
    15.         }
    16.         return minsum[0][0];
    17.     }
    18. };

  • 相关阅读:
    第三章 Flink基础理论之运行模式
    MyBatis介绍和基础案例（有代码）
    34 【表单和FormData 对象】
    如何评估产品说明书的质量和有效性
    最新基于 R 语言 lavaan 结构方程模型（SEM）实践技术应用
    RK3568开发笔记（十一）：开发版buildroot固件移植一个ffmpeg播放rtsp的播放器Demo
    Django REST项目实战：在线中文字符识别
    【MATLAB】羽状图
    MYSQL OPERATOR 容器化方案介绍
    前端css实现特殊日期网页变灰功能
  • 原文地址：https://blog.csdn.net/weixin_73961973/article/details/127625671