leadcode的Hot100系列--62. 不同路径--简单的动态规划
2024-10-02 01:18:01
题目比较清晰,简单来说就是:
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];
}
最新文章
- 使用vlc播放器做rtsp流媒体服务器
- 关于ubuntu下sublime text 3 的安装和中文配置问题
- 机器学习中的范数规则化之(一)L0、L1与L2范数
- js 百度地图
- 在Linux中安装Tomcat
- 使用OpenFileDialog会更改默认程序目录
- phpredis中文手册——《redis中文手册》 php版
- 无法加载协定为“ServiceReference1.xxxxx”的终结点配置部分,因为找到了该协定的多个终结点配置。请按名称指示首选的终结点配置部分
- java技术用ssh从linux服务器下载数据
- 数据结构-Hash表
- 2.4 Git 基础 - 撤消操作
- Windows Azure 即将更名
- rsync 只是测试,请看下一篇
- ftp服务器端的安装及配置
- JDBC 事务隔离级别
- iOS深入学习之Weak关键字介绍
- Visual Studio 2017无法加载Visual Studio 2015创建的SharePoint解决方案
- 安装MySQL容易出现的问题
- WPF 自定义TabControl控件样式
- _proto_理解