首页 > 其他分享 >动态规划(2)

动态规划(2)

时间:2024-01-16 10:59:07浏览次数:32  
标签:obstacleGrid return int vector 动态 规划 public dp

目录

63不同路径2

遇到障碍,说明该点无法到达,那么dp[i][j]=0

class Solution {
public:
    int slnA(vector<vector<int>>& obstacleGrid)
    {
        int m=obstacleGrid.size();
        int n=obstacleGrid[0].size();
        vector<vector<int>> dp(m,vector<int>(n,0));
        dp[0][0]=obstacleGrid[0][0]==0?1:0;
        for(int i=1;i<m;i++)
        {
            if(obstacleGrid[i][0]==1)
            {
                dp[i][0]=0;
            }
            else
                dp[i][0]=dp[i-1][0];
        }
        for(int j=1;j<n;j++)
        {
            if(obstacleGrid[0][j]==1)
            {
                dp[0][j]=0;
            }
            else
                dp[0][j]=dp[0][j-1];
        }
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                if(obstacleGrid[i][j]==1)
                {
                    dp[i][j]=0;
                }
                else{
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        return slnA(obstacleGrid);
    }
};

343整数拆分

class Solution {
public:
    /*
    dp数组的含义
    dp[n]表示拆分n所能达到的最大值
    最大值显然在dp[i-j]*j,(i-j)*j之间
    */
    int integerBreak(int n) {
        vector<int> dp(n+1);
        dp[2]=1;
        for(int i=3;i<=n;i++)
        {
            for(int j=1;j<=i/2;j++)
            {
                dp[i]=max(dp[i],max(dp[i-j]*j,(i-j)*j));
            }
        }
        return dp[n];
    }
};

96

class Solution {
public:
    /*
    dp数组含义,1到i为节点组成的二叉搜索树的个数为dp[i]
    初始化:dp[0]=0 dp[1]=1 dp[2]=2
    状态转移:dp[n]+=dp[i-j]*dp[j-1]
    */
    int numTrees(int n) {
        if(n==1)
        {
            return 1;
        }
        if(n==2)
        {
            return 2;
        }
        vector<int> dp(n+1);
        dp[0]=1;
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++)
        {
            for(int j=1;j<=i;j++)
            {
                dp[i]+=dp[j-1]*dp[i-j];
            }
        }
        return dp[n];

    }
};

标签:obstacleGrid,return,int,vector,动态,规划,public,dp
From: https://www.cnblogs.com/liviayu/p/17967051

相关文章

  • 山海鲸如何实现动态天气
    1.预设雨雪效果雨雪效果中的雨雪大小和雨雪覆盖如果不需要绑定数据,可以先预设好,这样后续切换后就可以有预设的大小,比如我们先将下雪的雪面覆盖设置成0.5。 设置完之后我们把天气设置为无。2.生成数据字段山海鲸中所有的组件属性都可以绑定动态数据,天气属性也不例外,首先我们......
  • 动态规划(1)
    目录动规基础509斐波那契数列746使用最小花费爬楼梯62不同路径写在前面,第二次刷动规,上次就有点没弄懂这次一定拿下了动规基础铭记动规五部曲:确定dp数组(dptable)以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组509斐波那契数列classSolution{......
  • 如何使用Java在Excel中添加动态数组公式?
    本文由葡萄城技术团队发布。转载请注明出处:葡萄城官网,葡萄城为开发者提供专业的开发工具、解决方案和服务,赋能开发者。前言动态数组公式是Excel引入的一项重要功能,它将Excel分为两种风格:Excel365和传统Excel(2019或更早版本)。动态数组功能允许用户从单个单元格中的公式......
  • 数学建模入门笔记(1)——Python pulp库解线性规划问题
    参考:Python求解线性规划——PuLP使用教程-Only(AR)-博客园(cnblogs.com)1.Definethemodelmodel=pl.LpProblem(name="",sense=pl.LpMaximize)name模型的名字sense模型的类型(pl.LpMaximize/pl.LpMinimize)2.Definethedecisionvariables用x[i]存储变量,命名为xi......
  • 精彩推荐 |【Java技术专题】「重塑技术功底」攻破Java技术盲点之剖析动态代理的实现原
    背景介绍在Java编程中,动态代理的应用非常广泛。它被广泛应用于SpringAOP框架、Hibernate数据查询、测试框架的后端mock、RPC以及Java注解对象获取等领域。静态代理和动态代理与静态代理不同,动态代理的代理关系是在运行时确定的,这使得它在灵活性上更胜一筹。相比之下,静态代理的代理......
  • SpringBoot动态权限校验,常用的实现方案
    SpringBoot.pngSpringBoot是由Pivotal团队提供的一套开源框架,可以简化spring应用的创建及部署。它提供了丰富的Spring模块化支持,可以帮助开发者更轻松快捷地构建出企业级应用。SpringBoot通过自动配置功能,降低了复杂性,同时支持基于JVM的多种开源框架,可以缩短开发时间,使开发更......
  • 编写一个小而强大的 Windows 动态屏保壁纸
    写在前面两年前我做了第一个开源软件DreamScene2动态桌面,如今受到了很多人的喜欢,这增加了我继续做好开源软件的信心。之前的这个软件一直有人希望我加入一个设置屏保壁纸的功能,因为DreamScene2就是一个单纯的动态桌面的软件,所以一直没有加入这个功能。今天我带来一个新的开源......
  • FreeSwitch: esl 调用lua动态传参&日志查看
    lua脚本在执行过程中,可动态接收参数,这样可以让系统更灵活,以上节的自动外呼为例,callout.lua改成下面这样:--主叫localcallernum=argv[1];--被叫localcalleenum=argv[2];freeswitch.consoleLog("info","debug==>caller:"..callernum..",callee:"..calleenum.......
  • Java 使用 数组实现 动态数组
    前述数组是各编程语言中最为基础的一个数据结构,在Java语言中,平时使用也很多,同时,JDK提供了动态数组的实现,ArrayList,这里我使用数组来实现一下动态数组,参考实现importjava.util.function.Consumer;/***使用数组实现动态数组ArrayList*/publicclassDynamicArray......
  • 非线性规划——Pyhton库的实现
    非线性规划(NonlinearProgramming,简称NLP)是一种优化问题的数学形式,其中目标函数或约束条件中至少有一个是非线性的。优化问题的目标是找到一组变量的取值,使得目标函数在满足一系列约束条件的情况下达到最小值或最大值。在非线性规划中,目标函数和约束条件可以包含平方项、绝对值、......