【动态规划】求二维数组走法路径种数

àì夳堔傛蜴生んèń 2022-08-09 09:42 139阅读 0赞

# 问题 #

给定二维数组，从左上走到右下的走法种树，数组中1代表该格可以走，0代表不能走。且只能向下和向右走。

# 解法 #

典型的动态规划问题：

dp[i][j]表示从[0][0]到[i][j]的走法数量。
    状态转移方程：
    dp[0][j] = 1  where i = 0
    dp[i][0] = 1  where j = 0
    dp[i][j] = dp[i-1][j] + dp[i][j-1] where arr[i][j] == 1
    dp[i][j] = 0   where arr[i][j] == 0

# 代码实现 #

int arr_path_nums(vector<vector<int> > arr,int M,int N)
    {
        int i,j;
        vector<vector<int> > dp(M,vector<int>(N,0));
        //初始条件
        for (i=0;i<M;i++)
            dp[i][0] = 1;
        for (j=0;j<N;j++)
            dp[0][j] = 1;
        for (i =1;i<M;i++)
        {
            for (j=1;j<N;j++)
            {
                if (arr[i][j] == 1)
                {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
                else if (arr[i][j] == 0)
                {
                    dp[i][j] = 0;
                }
                else
                    return -1;
            }
        }
        return dp[M-1][N-1];
    }

# 优化 #

本题依然可以用动态规划典型的空间优化方法，因为dp\[i\]\[j\]是依赖左边和上边的值的，所以可以申请一个大小为N的数组，每次从后到前遍历即可。代码就不用给出了，很简单。

发表评论取消回复

表情：

评论列表（有 0 条评论，139人围观）

还没有评论，来说两句吧...

相关阅读

相关【动态规划】求二维数组走法路径种数

问题给定二维数组，从左上走到右下的走法种树，数组中1代表该格可以走，0代表不能走。且只能向下和向右走。解法典型的动态规划问题： dp[i][j]表

àì夳堔傛蜴生んèń/ 2022年08月09日 09:42/ 0 赞/ 140 阅读

相关【动态规划】求一维子数组的最大和

题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如，输

傷城~/ 2022年08月09日 00:59/ 0 赞/ 162 阅读

相关【动态规划】求二维数组从左下到右上的最优路径

1.求二维数组从左下到右上的最优路径，使得路径和最大，并且只能向上或向下走。解析：求最短路径，路径和最优等都可以用动态规划做。 dp\[i\]\[j\]表示到i，j坐

古城微笑少年丶/ 2022年08月09日 00:58/ 0 赞/ 109 阅读

相关取得动态二维数组

在C语言中，有内置的一维数组，二维数组等多维数组，也可以使用动态分配内存的方式，很容易的得到一个类似内置静态一维数组的动态数组（在这里我这么叫，也许并不存在这个定义 :)

深藏阁楼爱情的钟/ 2022年08月04日 04:03/ 0 赞/ 169 阅读

相关二维数组动态分配

代码转自：http://blog.csdn.net/lifanxi/article/details/1649840 include <iostream> in

àì夳堔傛蜴生んèń/ 2022年07月16日 11:48/ 0 赞/ 169 阅读

相关网格走法种数

题目描述有一个X\Y的网格，小团要在此网格上从左上角到右下角，只能走格点且只能向右或向下走。请设计一个算法，计算小团有多少种走法。给定两个正整数int x,int y，

水深无声/ 2022年06月09日 11:15/ 0 赞/ 116 阅读

相关动态申请二维数组

方法一： // EX_EXAM.cpp : 定义控制台应用程序的入口点。 // include "stdafx.h" include

谁践踏了优雅/ 2022年05月27日 08:54/ 0 赞/ 173 阅读

相关动态开辟二维数组

c float H1=NULL; for (int k = 0; k < N; ++k) { H1[k] = (fl

比眉伴天荒/ 2022年05月27日 05:05/ 0 赞/ 145 阅读

相关求二维数组蓄水数

1、需求接上一个需求：[求一维数组蓄水数][Link 1]，如果数组是二维数组呢？如果求得蓄水数呢？比如这种情况：红色的格子是能蓄水的格子，蓝色的各自是墙，也

逃离我推掉我的手/ 2022年01月09日 23:07/ 0 赞/ 204 阅读

相关求一维数组蓄水数

1、需求很多程序员在面试的时候，都可能遇到一些逻辑思维/编程题，这样的题目非常有意思。而且非常考验程序员的解题技巧和代码编写能力。我这儿就曾经遇到过一个。具体需求看

太过爱你忘了你带给我的痛/ 2022年01月09日 22:37/ 0 赞/ 196 阅读