1.定义问题
2.找递归式
3.初始化
一、 爬楼梯
描述
假设你正在爬楼梯。需要 n 步你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
- 1 步 + 1 步
- 2 步
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
- 1 步 + 1 步 + 1 步
- 1 步 + 2 步
- 2 步 + 1 步
思路
1.f(n)表示上n阶台阶的方式数
2.f(n)=f(n-1)+f(n-2)
上第n阶台阶，有两种情况，从n-1阶台阶上去，从n-2阶台阶上去。第一种情况有f(n-1)种走法，第二种情况有f(n-2)种走法，因此f(n-1)+f(n-2)就是上第n阶台阶的走法
3.f(1)=1,f(2)=2
从头累加到n
AC代码
var climbStairs = function(n) {
var x1=1,x2=2,xn=0
if(n==1)return 1
if(n==2)return 2
for(let i=3;i<=n;i++){
xn=x1+x2
x1=x2
x2=xn
}
return xn
};
二、打家劫舍
描述
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:
输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
思路
1.rob[i]表示偷第0-i家获取的最高金额
2.rob[i]=MAX(rob[i-2]+nums[i]，rob[i-1])
偷0-i家，可以偷到i-1家，也可以偷到i-2家和第i家，两种偷法选出最大金额即为偷0-i家的最大金额
AC代码
var rob = function(nums) {
var len=nums.length,rob=[]
if (len<1) return 0
rob[0]=nums[0]
rob[1]=Math.max(nums[0],nums[1])
for(var i=2;i<len;i++){
rob[i]=Math.max(rob[i-1],rob[i-2]+nums[i])
}
return rob[len-1]
};
三、走格子
描述
有一个机器人的位于一个 m × n 个网格左上角。
机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角。
问有多少条不同的路径？
样例
给出 m = 3 和 n = 3, 返回 6.
给出 m = 4 和 n = 5, 返回 35.
解决步骤
1、定义dp[n][m]是：机器人从 m × n 个网格左上角走到网格的右下角中的所有不同路径数
2、dp[n][m]=dp[n-1][m]+dp[n][m-1]
机器人要么右移要么下移，所有路径数是这两种走法之和。当机器人右移时，他还需要面对n-1*m个格子，而这个网格的走法也是右移和下移，同理机器人下移。
3、初始化。需要初始化n-1=0,m任意的情况和m-1=0，n任意的情况，m,n从2开始循环
当n=1,m=1 时，dp[1][1]=1
当n>1,m=1时，dp[n][1]=dp[n-1][1]
当n=1,m>1时，dp[1][m]=dp[1][m]
代码
function paths(n,m){
//初始化一维数组
var dp=[]
//初始化二维数组
for(let i=0;i<n;i++){
dp[i]=[]
}
if(n<1||m<1)return 0
for(let i=0;i<n;i++){
for(let j=0;j<m;j++){
if(i==0&&j==0)
dp[i][j]=1
else if(i==0&&j>0)
dp[i][j]=dp[i][j-1]
else if(i>0&&j==0)
dp[i][j]=dp[i-1][j]
else if(i>0&&j>0)
dp[i][j]=dp[i-1][j]+dp[i][j-1]
}
}
return dp[n-1][m-1]
}
网友评论