动态规划入门之走方格

静谧星空TEL

发布于 2021-04-27 11:27:13

6250

文章被收录于专栏：云计算与大数据技术云计算与大数据技术

一、问题描述

给定一个 m x n 的棋盘，只能向右或者向下走，，求棋子从左上角走到右下角的情况一共有多少种?

二、解题思路

这是一个动态规划求解的问题，原问题的解可以由子问题求解。

状态转移方程：f[m][n] = f[m-1][n]+f[m][n-1]

动态规划不一定会用带递归，而且递归容易栈溢出，双重for循环直接从底层向上求解即可。

注意第一行和第一列的值都为1，因为一直往右走或者往下走只有一种情况。

三、代码实现

public class Maze {

	public static void main(String[] args) {
		int result = new Maze().f(8, 8);
		System.out.println(result);
	}
	public int f(int m,int n) {
		int [][]f = new int[m][n];
		for(int i=0;i

`四、运行结果`

1	1	1	1	1	1	1	1	
1	2	3	4	5	6	7	8	
1	3	6	10	15	21	28	36	
1	4	10	20	35	56	84	120	
1	5	15	35	70	126	210	330	
1	6	21	56	126	252	462	792	
1	7	28	84	210	462	924	1716	
1	8	36	120	330	792	1716	3432	
3432

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/02/23 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

动态规划入门之走方格

动态规划入门之走方格

一、问题描述

二、解题思路

三、代码实现

`四、运行结果`

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐