动态规划做题步骤:
1.定义状态
2.编写状态转移方程
3.设置初始值
例题(青蛙跳台阶问题):
题目描述:
一只青蛙一次可以跳上
1
级台阶,也可以跳上
2
级。求该青蛙跳上一个
n
级的台阶总共有多少种跳法(先后次序不同算 不同的结果)
题目分析:
1.定义状态
? f(n):青蛙跳上第n级台阶总跳法数
2.状态转移方程:
? f(n)=f(n-1) + f (n-2)
3.设置初始值:
? f(0)=1? ? f(1)=1? ??f(2)=2
代码实现:
public class Solution {
public int jumpFloor(int target) {
//f(n)=f(n-1)+f(n-2)
int[] dp=new int[target+1];
dp[0]=1;//0台阶,就是起点,到达0台阶的方法有一种,就是不跳[这里可能有点奇怪,但是想想,如果方法次数为0,就说明不可能开始...]
dp[1]=1;
for(int i=2;i<=target;i++){
dp[i]=dp[i-1]+dp[i-2];
}
return dp[target];
}
}
怎么使用动规:
一般使用动规,必定使用数组(一维,二维)
|