1.上楼梯

题目描述

有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶、3阶。请实现一个方法，计算小孩有多少种上楼的方式。为了防止溢出，请将结果Mod 1000000007

给定一个正整数int n，请返回一个数，代表上楼的方式数。保证n小于等于100000。

测试样例：

1

返回：1

类似这种上楼梯的题目都可以用动态规划或者递归来做，首先要用数学归纳法找出通项公式

方法1：不断往n迭代推进

import java.util.*;

public class GoUpstairs {

    public int countWays(int n) {

        int dp1=1,dp2=2,dp3=4;

        if(n==1)return dp1;

        if(n==2)return dp2;

        if(n==3)return dp3;

        int result=0;

        int temp=0;

        for(int i=4;i<=n;i++){

            temp=(dp1+dp2)%1000000007;//注意：此处原先没加取模运算,则报错

            result=(temp+dp3)%1000000007;

            //不断向n推进

            dp1=dp2;

            dp2=dp3;

            dp3=result;

        }

return result;        

    }

}

方法2：利用数组下标（动态规划）

import java.util.*;

public class GoUpstairs {

    public int countWays(int n) {

        int nums[]=new int[n];

        //角标变了最后元素在为nums[n-1]

        nums[0]=1;

        nums[1]=2;

        nums[2]=4;

        for(int i=3;i<n;i++){

            nums[i]=((nums[i-3]+nums[i-2])%1000000007+nums[i-1])%1000000007;

        }

        return nums[n-1];

    }

}

2.机器人走方格I

题目描述

有一个XxY的网格，一个机器人只能走格点且只能向右或向下走，要从左上角走到右下角。请设计一个算法，计算机器人有多少种走法。

给定两个正整数int x,int y，请返回机器人的走法数目。保证x＋y小于等于12。

测试样例：

2,2

返回：2

方法1：递归解法

思想： 机器人在X*Y的矩阵中走，每一步都有两种选择：要么向下、要么向右。如果向下走，问题就变成：求(X-1)*Y矩阵中机器人的走法；

     如果向右走，问题就变成：求X*(Y-1)矩阵中机器人的走法；到达最后一个格点回退。（最后一个点坐标(1,1),开始写(0,0)始终编译不过）

import java.util.*;

public class Robot {

    public int countWays(int x, int y) {

        if(x==0||y==0)return 0;

        if(x==1||y==1)return 1;

        else

            return countWays(x-1,y)+countWays(x,y-1);

    }

}

方法2：动态规划

大格子两条边的走法只有1条，每个小格子countWays(x, y)=countWays(x-1, y)+countWays(x, y-1)

import java.util.*;

public class Robot {

    public int countWays(int x, int y) {

        int dp[][]=new int[x][y];

        for(int i=0;i<x;i++){

            dp[i][0]=1;

        }

        for(int i=0;i<y;i++){

            dp[0][i]=1;

        }

        for(int i=1;i<x;i++){

            for(int j=1;j<y;j++){

                dp[i][j]=dp[i][j-1]+dp[i-1][j];

            }

        }

        return dp[x-1][y-1];

    }

--------------------- 

作者：InGodWeTrust_kwz 

来源：CSDN 

原文：https://blog.csdn.net/sinat_22797429/article/details/75734839 

版权声明：本文为博主原创文章，转载请附上博文链接！