欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

leadcode的Hot100系列--62. 不同路径--简单的动态规划

程序员文章站 2022-05-18 21:19:16
题目比较清晰,简单来说就是: | A | B | C | D | | | | | | | E | F | G | H | | I | J | K | L | 只能往右或者往下,从A到L,能有几种走法。 这里使用动态规划的方法来做一下。 动态规划最重要的就是动态方程,这里简单说下这个动态方程怎么做出来 ......

题目比较清晰,简单来说就是:

a b c d
e f g h
i j k l

只能往右或者往下,从a到l,能有几种走法。
这里使用动态规划的方法来做一下。
动态规划最重要的就是动态方程,这里简单说下这个动态方程怎么做出来的吧。


记 f(b) 为 a到b总共可以有的走法。
想知道f(l),那其实只要知道f(h)和f(k)就可以了。
因为从a到h之后,再想到l就只有一种方法,ak同理,所以 f(l) = f(h) + f(k)。

那f(h)呢,就等于 f(d)+f(g),这里就很容易得到他的动态方程:

f [i] [j] = f [i] [j-1] + f [i-1] [j] // i 代表行,j 代表列

得到状态方程之后,最后再考虑一下边界的情况,也就是 f(a) f(b) f(e) f(i) 等。
因为题目已经规定了,只能往右走,或者往下走,
所以第一行的走法都是只有1,第一列的走法也是只有1,可以得到:

1 1 1 1
1 f(f) f(g) f(h)
1 f(j) f(k) f( l)

so:f(f) = f(b) + f(e) = 1 + 1 = 2
f(g) = f(c) + f(f) = 1 + 2 = 3
f(h) = f(d) + f(g) = 1 + 3 = 4
f(j) = f(i) + f(f) = 1 + 2 = 3
f(k) = f(g) + f(j) = 3 + 3 = 6
f(l) = f(h) + f(k) = 4 + 6 = 10

这里附上代码:

int uniquepaths(int m, int n){
    int dp[100][100]={0}, i, j;
    for (i=0; i<m; i++)     // 这里初始化第一列的走法为1
        dp[i][0] = 1;
    for (i=0; i<n; i++)   // 这里初始化第一行的走法为1
        dp[0][i] = 1;
    
    for (i=1; i<m; i++)
    {
        for (j=1; j<n; j++)
        {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];   // 动态方程
        }
    }
    
    return dp[m-1][n-1];
    
}