二维DP问题-程序员宅基地

文章目录

前言
小技巧
例题 1
- 方法一求组合数
- 方法二动态规划
例题 2
- 方法一 dp
例题 3
- 方法一 dp

前言

我们经常会碰到二维DP问题，比如给你一张地图（一般是二维矩阵），让你计算出从地图的左上端走到右下端的路径有多少条 / 最短的路径之和，这种问题一般会被限制运动的空间（至少我现在所碰到的题目），一般是只能向下和向右移动。

我对dp问题理解不深，对于二维dp问题我的理解就是找出最优子结构（递推方程）之后，用一个二维数组来保存历史状态就能解决问题了

小技巧

一般这种问题很容易被矩阵上边和左边这两条boundary把程序搞得很复杂（因为这两个boundary需要修改特定的递推公式程序），我们在开辟二维dp数组时，把长和宽都+1，然后从（i，j）=（1，1）开始遍历，这样就不会遇到boundary问题了

其次就是dp数组压缩，我们可以观察到，其实我们的二重嵌套循环就是每次循环一行，然后对于这一行的每一个元素，都根据他的dp[left]和dp[up]来对他进行更新，而我们可以使用一个映射，将这种二维关系（dp[left]和dp[up]）映射成一维关系（意思就是我们只用使用一个一维的DP数组即可）

比如

if col == 0
	dp[col] = f(dp[col])// 这是因为现在的dp[up]就是dp[col]，而col=0时，dp[col]的左边没东西
else 
	dp[col] =  f(dp[col-1], dp[col])//这是因为此时 dp[left] = dp[col-1], dp[up] = dp[col]

通过上面的伪代码，你一定明白了如何将二维dp数组压缩为一维dp数组吧

例题 1

这是非常经典的一道二维dp题目了，我们的解决方法有两种：求组合数和DP求解。

DP求解的话，这个问题的最优子结构为：
$d p [c u r r] = d p [l e f t] + d p [u p]$

62. Unique Paths
There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

Example 1:
在这里插入图片描述

Input: m = 3, n = 7
Output: 28
Example 2:

Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

方法一求组合数

因为机器人只能向右或者向下走，而机器人一共要走 width + height 步，所以总的走法就是一个组合数 : C(n, m)，其中n为height+weight， m为weight或者height

class Solution {
   
    
public:
    int uniquePaths(int m, int n) {
   
    
        if(m == 1 || n == 1)
            return 1;
        m--, n--;
        if(m < n) swap(m, n);
        long res = 1;
        for(int i = m+1, j

本文链接：https://blog.csdn.net/NP_hard/article/details/123457205

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

[UE4]UMG widget Property Binding(属性绑定)，事件触发蓝图函数和C++函数-程序员宅基地

文章浏览阅读2.8k次，点赞3次，收藏3次。假如用UMG绘制了一个button类型的widget，然后我们想让这个button的状态变化与相关属性或者函数绑定，则参考官方的文档如下： Property Binding（如何绑定蓝图属性和蓝图函数）https://docs.unrealengine.com/latest/INT/Engine/UMG/UserGuide/PropertyBinding/index.htmlH..._binding: property ' /script/umg.widget:visibilitydelegate ' on widget ' butt

音视频系列1：流媒体_hds akamai-程序员宅基地

文章浏览阅读1.3k次。1. 使用vlc，自带server安装好vlc软件，然后用如下命令起流Applications/VLC.app/Contents/MacOS/VLC -vvv test.264 –sout ‘#rtp{sdp=rtsp://:5544/test}’;vlc会自动创建server，不错哦。2. 使用ffmpeg，nginx做server参考这里mac貌似自带ffmpeg，没有的话就安装一个，然后ffmpeg -re -i test.mp4 -vcodec copy -codec copy -_hds akamai

pytorch 之 nn.BatchNorm2d(oup)( 100 )_batchnorm2d(100)-程序员宅基地

文章浏览阅读2w次，点赞2次，收藏9次。先看看解释。。。。。然后。。。我的疑惑在于：网络片段：nn.Conv2d(inp, oup, 3, stride, 1, bias=False),nn.BatchNorm2d(oup),nn.ReLU(inplace=True),我打印model的parameters来查看参数：打印的为：0.conv.0.weight ： torch.Size([32, 3, 3, 3])0.conv.1...._batchnorm2d(100)

MATLAB 画图，对数坐标轴_matlab 对数轴-程序员宅基地

文章浏览阅读1w次，点赞6次，收藏23次。对数坐标轴_matlab 对数轴

迟到的第一篇博客-程序员宅基地

文章浏览阅读194次。其实很早之前就一直在使用CSDN论坛查阅资料，学习新知识。但是直到2019年下旬才注册了账号，当时是因为每天看到不同的大牛博主更新的博文点燃了我的创作激情（毕竟我初中时做过语文课代表），结果注册了账号之后因为工作比较忙碌，也就没有维护。（当初的豪言壮语早被抛掷脑后）先说说自己的情况吧，本人，男，老家来自陕西渭南（谁在说我们渭南没程序猿我跟谁急），之前的专业是法律事务，至于为什么会踏上程序猿这条不归路我以后还会再讲，现在在北京北漂工作一年多了，目前刚刚从上家公司跳槽，现在在一家私企做linux系统开发。因为

PIC18F47K42 初学篇-1_pic18f46k40 学习-程序员宅基地

文章浏览阅读795次。5月1日开始学习PIC18系列单片机，之前一直用MSP430的16位单片机，技能总是太单一，稳定性不是很好。决定回到8位PIC来看看，从PIC18F47K42开始吧，有一个小红板方便开始学习，配合官网资料、手把手教你学PIC单片机、PIC微控制器项目设计。书本主要是加速作用，并没有推荐意义。MPLAB X IDE应该来说还是很不错，就是占用内存太多，运行时硬盘咳咳作响。MCC配置功能还..._pic18f46k40 学习

随便推点

! [rejected] master -＞ master (non-fast-forward)解决方案_ios ! [rejected] main -> master (non-fast-forward)-程序员宅基地

文章浏览阅读382次。解决方案：强制上传 git push -f origin master如果github或gitee没有其他人在修改，用这个没什么影响，但是如果还有其他人修改了，用-f命令会覆盖掉他的修改，慎用。_ios ! [rejected] main -> master (non-fast-forward)

PoseCNN: A Convolutional Neural Network for 6D Object Pose Estimation in Cluttered Scenes—2017（笔记）-程序员宅基地

文章浏览阅读1.6k次，点赞2次，收藏7次。PoseCNN：用卷积神经网络估计杂乱场景中目标6D姿态—2017（笔记）文章提出了新的PoseCNN姿态估计网络，通过CNN提取图像特征，然后分三路进行目标分割标签标注、平移估计和姿态估计得到目标6D姿态，其中通过应用新型损失函数，能够较好地估计对称目标。 ----------------- Occlusion、symmetric object、only RGB摘要..._posecnn: a convolutional neural network for 6d object pose estimation in clu