段誉身具凌波微波，动无常则，若危若安，一次能走一级台阶或者两级台阶，他要爬一段30级的山路，问有多少种走法？分析如何计算，然后编程解答。
进阶问题：当他轻功熟练度提升，一次最多可以走三级，那就结果有什么变化？后来走火入魔了，不能走一级，只能走二或三级，又有什么变化？
[编程题]序号6
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
//本题n较小，所以递归也可以，但如果n较大则会超时，所以通用解法为动态规划
vector<int>dp1(n+1),dp2(n+1),dp3(n+1);
vector<int>res(3);
if(n==1) {cout<<1<<" "<<1<<" "<< 0;return 0;}
if(n==2){cout<<2<<" "<<2<<" "<<1;return 0;}
//第一种情况
dp1[0]=1;
dp1[1]=1;
for(int i=2;i<=n;i++)
{
dp1[i]=dp1[i-1]+dp1[i-2];
}
res[0]=dp1[n];
//第二种情况
dp2[0]=1;
dp2[1]=1;
dp2[2]=2;
for(int i=3;i<=n;i++)
{
dp2[i]=dp2[i-1]+dp2[i-2]+dp2[i-3];
}
res[1]=dp2[n];
//第三种情况
dp3[0]=0;
dp3[1]=0;
dp3[2]=1;
dp3[3]=1;
for(int i=4;i<=n;i++)
{
dp3[i]=dp3[i-2]+dp3[i-3];
}
res[2]=dp3[n];
cout<<res[0]<<" "<<res[1]<<" "<<res[2];
return 0;
}
发表于 2020-07-17 11:53:59
回复(0)
#include <iostream>
using namespace std;
int L1(int num){
if(num==0) return 1;
else if(num<0) return 0;
return L1(num-1)+L1(num-2);
}
int L2(int num){
if(num==0) return 1;
else if(num<0) return 0;
return L2(num-1)+L2(num-2)+L2(num-3);
}
int L3(int num){
if(num==0) return 1;
else if(num<0) return 0;
else return L3(num-3)+L3(num-2);
}
int main(){
int n;
cin>>n;
cout<<L1(n)<<" "<<L2(n)<<" "<<L3(n);
system("pause");
return 0;
}
发表于 2020-03-12 12:14:07
回复(0)
简单递归题，直接上代码
#include <iostream>
#include <string.h>
using namespace std;
int dfs1(int num){
if(num == 0) return 1;
if(num < 0) return 0;
return dfs1(num - 1) + dfs1(num - 2);
}
int dfs2(int num){
if(num == 0) return 1;
if(num < 0) return 0;
return dfs2(num - 1) + dfs2(num - 2) + dfs2(num - 3);
}
int dfs3(int num){
if(num == 0) return 1;
if(num < 0) return 0;
return dfs3(num - 2) + dfs3(num - 3);
}
int main() {
int n, a, b, c;
cin >> n;
a = dfs1(n);
b = dfs2(n);
c = dfs3(n);
cout << a << ' ' << b << ' ' << c << endl;
return 0;
}
发表于 2020-02-10 21:33:52
回复(0)
JavaScript(Node) 😎题目:4399👾-dp dp dp
const readline = require('readline')
const rl = readline.createInterface({
input: process.stdin,
ouput: process.stdout
})
let inArr = []
rl.on('line', line=>{
if(!line) return
inArr.push(line.trim())
if(inArr.length === 1){
let n = +inArr[0]
let res = [dp1(n),dp2(n),dp3(n)]
console.log(res.join(' '))
}
})
function dp1(n){
let dp = [1,1,2]
for (let i = 3; i < n+1; i++) {
dp[i] = dp[i-1]+dp[i-2]
}
return dp[n]
}
function dp2(n){
let dp = [1,1,2,4]
for (let i = 4; i < n+1; i++) {
dp[i] = dp[i-1]+dp[i-2]+dp[i-3]
}
return dp[n]
}
function dp3(n){
let dp = [0,0,1,1]
for (let i = 4; i < n+1; i++) {
dp[i] = dp[i-3]+dp[i-2]
}
return dp[n]
}
发表于 2020-03-09 15:20:11
回复(0)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int stairs = in.nextInt();
int res1 = climbStairs1(stairs);
int res2 = climbStairs2(stairs);
int res3 = climbStairs3(stairs);
System.out.printf("%d %d %d", res1, res2, res3);
}
// 将爬楼梯问题转化为完全背包
// 背包为楼梯数，物品为段誉每次可以选择的走法
public static int climbStairs1(int target) {
int[] dp = new int[target+1];
int[] choose = {1, 2};
dp[0] = 1;
// 求排列，先遍历背包，再遍历物品
// 正序遍历
for (int i=0; i<=target; i++) {
for (int j=0; j<choose.length; j++) {
if (i >= choose[j]) {
dp[i] += dp[i - choose[j]];
}
}
}
return dp[target];
}
public static int climbStairs2(int target) {
int[] dp = new int[target+1];
int[] choose = {1, 2, 3};
// dp[0] 无意义，为了满足计算公式设为1
dp[0] = 1;
for (int i=0; i<=target; i++) {
for (int j=0; j<choose.length; j++) {
if (i >= choose[j]) {
dp[i] += dp[i - choose[j]];
}
}
}
return dp[target];
}
public static int climbStairs3(int target) {
int[] dp = new int[target+1];
int[] choose = {2, 3};
dp[0] = 1;
for (int i=0; i<=target; i++) {
for (int j=0; j<choose.length; j++) {
if (i >= choose[j]) {
dp[i] += dp[i - choose[j]];
}
}
}
return dp[target];
}
}
发表于 2023-04-05 15:32:08
回复(0)
#include <bits/stdc++.h>
using namespace std;
int main()
{
int dp[3][50];
int n;cin >> n;
dp[0][0]=dp[1][0]=dp[2][0]=1;
for(int i=1;i<=n;i++)
{
dp[0][i]=((i-1>=0)?dp[0][i-1]:0)+((i-2>=0)?dp[0][i-2]:0);
dp[1][i]=((i-1)>=0?dp[1][i-1]:0)+((i-2>=0)?dp[1][i-2]:0)+((i-3>=0)?dp[1][i-3]:0);
dp[2][i]=((i-3>=0)?dp[2][i-3]:0)+((i-2>=0)?dp[2][i-2]:0);
}
cout << dp[0][n] << " " << dp[1][n] << " " << dp[2][n] << endl;
} 比较简短的线性DP代码
发表于 2022-09-20 16:20:08
回复(0)
簡單動規題：
C#：26ms、34.28MB
using System;
public class Program{
public static void Main(){
int n = Convert.ToInt32(Console.ReadLine());
int[] dp_a = new int[n + 1];
int[] dp_b = new int[n + 1];
int[] dp_c = new int[n + 1];
Console.Write(StepOneAndTwo(n, dp_a) + " " +
StepOneTwoThree(n, dp_b) + " " +
StepTwoThree(n, dp_c));
}
//走一步和兩步
public static int StepOneAndTwo(int stepLeft, int[] dp)
{
if(stepLeft < 0) { return 0; }
if(stepLeft == 0) { return 1; }
if(dp[stepLeft] != 0) { return dp[stepLeft]; }
int result =
StepOneAndTwo(stepLeft - 1, dp) +
StepOneAndTwo(stepLeft - 2, dp);
dp[stepLeft] = result;
return dp[stepLeft];
}
//走一、二、三步
public static int StepOneTwoThree(int stepLeft, int[] dp)
{
if(stepLeft < 0) { return 0; }
if(stepLeft == 0) { return 1; }
if(dp[stepLeft] != 0) { return dp[stepLeft]; }
int result =
StepOneTwoThree(stepLeft - 1, dp) +
StepOneTwoThree(stepLeft - 2, dp) +
StepOneTwoThree(stepLeft - 3, dp);
dp[stepLeft] = result;
return dp[stepLeft];
}
//走兩步、三步
public static int StepTwoThree(int stepLeft, int[] dp)
{
if(stepLeft < 0) { return 0; }
if(stepLeft == 0) { return 1; }
if(dp[stepLeft] != 0) { return dp[stepLeft]; }
int result =
StepTwoThree(stepLeft - 2, dp) +
StepTwoThree(stepLeft - 3, dp);
dp[stepLeft] = result;
return dp[stepLeft];
}
}
编辑于 2021-03-27 16:24:09
回复(0)
#include<iostream>
#include<vector>
using namespace std;
int main(){
int n , a, b, c;
cin>>n;
vector<int> dp1(n + 1, 0);
vector<int> dp2(n + 1, 0);
vector<int> dp3(n + 1, 0);
//初始化
dp1[1] = 1 ,dp1[2] = 2;
dp2[1] = 1 ,dp2[2] = 2, dp2[3] = 4;
dp3[1] = 0 ,dp3[2] = 1, dp3[3] = 1;
//思想，dp[i] = dp[i-1]+d[i-2];
if(n <= 2){
a = dp1[n];
b = dp2[n];
c = dp3[n];
}
else{
for(int i = 3; i <= n ; i++){
dp1[i] = dp1[i - 1] + dp1[i -2];
}
a = dp1[n];
for(int i = 4; i <= n; i++){
dp2[i] = dp2[i - 1] + dp2[i -2] + dp2[i -3];
}
b = dp2[n];
for(int i = 4; i <= n; i++){
dp3[i] = dp3[i - 2] + dp3[i - 3];
}
c = dp3[n];
}
cout<< a << " "<< b << " "<< c;
return 0;
}
发表于 2020-10-26 15:50:41
回复(0)
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int [] a = new int [31];
a[1] = 1;a[2] =2;
int [] b = new int [31];
b[1]= 1;b[2] = 2; b[3] =4;
int [] c = new int [31];
c[2] = 1; c[3] =1;
for(int i =3 ; i<=n ;i++) {
a[i] = a[i-1]+a[i-2];
if(i>3) {
b[i] = b[i-1] + b[i-2] + b[i-3];
c[i] = c[i-2] + c[i-3];
}
}
System.out.println(a[n] +" " + b[n] +" "+ c[n]); 摸鱼过来
发表于 2025-08-13 14:39:22
回复(0)
// 递归加记忆化搜索剪枝，改一改就是动态规划了
using System;
using System.Collections;
using System.Collections.Generic;
public class Program {
public static void Main() {
string line = System.Console.ReadLine ();
int a = int.Parse(line);
if (a == 1) {
Console.WriteLine("1 1 0");
} else {
Console.WriteLine(
$"{dpsOne(a,new Dictionary<int,int>())} {dpsTwo(a,new Dictionary<int,int>())} {dpsThree(a,new Dictionary<int,int>())}");
}
}
private static int dpsOne(int stage, Dictionary<int, int> dic) {
if (dic.ContainsKey(stage))return dic[stage];
if (stage == 1 || stage == 2) return stage;
int stage_1 = dpsOne(stage - 1, dic);
if (!dic.ContainsKey(stage - 1)) {
dic.Add(stage - 1, stage_1);
}
int stage_2 = dpsOne(stage - 2, dic);
if (!dic.ContainsKey(stage - 2)) {
dic.Add(stage - 2, stage_2);
}
return dic[stage - 1] + dic[stage - 2];
}
private static int dpsTwo(int stage, Dictionary<int, int> dic) {
if (dic.ContainsKey(stage))return dic[stage];
if (stage == 1 || stage == 2) return stage;
if (stage == 3) return 4;
int stage_1 = dpsTwo(stage - 1, dic);
if (!dic.ContainsKey(stage - 1)) {
dic.Add(stage - 1, stage_1);
}
int stage_2 = dpsTwo(stage - 2, dic);
if (!dic.ContainsKey(stage - 2)) {
dic.Add(stage - 2, stage_2);
}
int stage_3 = dpsTwo(stage - 3, dic);
if (!dic.ContainsKey(stage - 3)) {
dic.Add(stage - 3, stage_3);
}
return dic[stage - 1] + dic[stage - 2] + dic[stage - 3];
}
private static int dpsThree(int stage, Dictionary<int, int> dic) {
if (dic.ContainsKey(stage))return dic[stage];
if (stage == 2 || stage == 3 || stage == 4) return 1;
int stage_2 = dpsThree(stage - 2, dic);
if (!dic.ContainsKey(stage - 2)) {
dic.Add(stage - 2, stage_2);
}
int stage_3 = dpsThree(stage - 3, dic);
if (!dic.ContainsKey(stage - 3)) {
dic.Add(stage - 3, stage_3);
}
return dic[stage - 2] + dic[stage - 3];
}
}
发表于 2024-03-09 04:47:09
回复(0)
import java.util.*;
import java.io.*;
public class Main{//青蛙跳台阶的翻版
public static void main(String []args)throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int n=Integer.parseInt(br.readLine());
if(n==1){
System.out.print("1 1 0");
return;
}
if(n==2){
System.out.print("2 2 1");
return;
}
if(n==3){
System.out.print("3 4 1");
return;
}
int[] nums_1=new int[n],nums_2=new int[n],nums_3=new int[n];
nums_1[0]=1;nums_1[1]=2;nums_1[2]=3;
nums_2[0]=1;nums_2[1]=2;nums_2[2]=4;
nums_3[0]=0;nums_3[1]=1;nums_3[2]=1;
for(int i=3;i<n;i++){
nums_1[i]=nums_1[i-1]+nums_1[i-2];
nums_2[i]=nums_2[i-1]+nums_2[i-2]+nums_2[i-3];
nums_3[i]=nums_3[i-3]+nums_3[i-2];
}
System.out.println(nums_1[n-1]+" "+nums_2[n-1]+" "+nums_3[n-1]);
}
}
发表于 2022-08-18 17:04:00
回复(0)
俺用的应该叫回溯..？
#include<iostream>
using namespace std;
int ways[3]={0,0,0};//统计三种轻功的走法数量
void backTrace(int x,int n,int type,int *qingong){
//x=走到第几个阶梯，n=拢共有多少层阶梯，type=段誉只会第几种轻功, qingong=***详情
if(x==n){//登顶了
ways[type]++;//记录一下走法数量
return ;
}
//轻功有几种跨阶梯方式
int size =2;
if(type==1) size+=1;
for(int i=0;i<size;++i){
if(x+qingong[i]>n) continue;//不作无用功
backTrace(x+qingong[i],n,type,qingong);//没登顶，继续施展轻功
}
}
int main(){
int n;
cin>>n;//输入
//轻功***图谱
int a[2]={1,2};
int b[3]={1,2,3};
int c[2]={2,3};
//用上述几种轻功尝试登顶，并记录次数
backTrace(0,n,0,a);
backTrace(0,n,1,b);
backTrace(0,n,2,c);
//输出
cout<<ways[0]<<" "<<ways[1]<<" "<<ways[2]<<endl;
return 0;
}
编辑于 2022-02-27 17:28:49
回复(0)
典型动态规划问题-爬楼梯
采用三个动态规划数组解决问题，核心思想是根据每一步能上的台阶数将当前台阶的状态转化为几个旧状态数值的和。
#include<iostream>
#include<vector>
using namespace std;
int main() {
int n;
while (cin >> n) {
vector<int> a(n + 1, 0);
vector<int> b(n + 1, 0);
vector<int> c(n + 1, 0);
a[0] = b[0] = c[0] = 1;
a[1] = b[1] = 1;
c[1] = 0;
if (n == 1) {
cout << a[1] << ' ' << b[1] << ' ' << c[1] << endl;
continue;
}
a[2] = a[1] + a[0];
b[2] = b[1] + b[0];
c[2] = c[0];
for (int i = 3; i <= n; i++) {
a[i] = a[i - 1] + a[i - 2];
b[i] = b[i - 1] + b[i - 2] + b[i - 3];
c[i] = c[i - 2] + c[i - 3];
}
cout << a[n] << ' ' << b[n] << ' ' << c[n] << endl;
}
return 0;
}
发表于 2021-08-23 16:06:32
回复(0)
import java.util.Scanner;
/**
* @author NHGA
* @creat 2020-10-23-17:00
*/
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
System.out.println(demo01(n)+" "+demo02(n)+" "+demo03(n));
}
//走一步或两
public static int demo01(int n){
if(n==1) return 1;
if(n==2) return 2;
int[] f=new int[n+1];
f[0]=0;//零阶台阶
f[1]=1;//一阶台阶
f[2]=2;//两阶台阶
/*i阶台阶*/
for (int i=3;i<=n;i++){
f[i]=f[i-1]+f[i-2];
}
return f[n];
}
//走一步或两或三
public static int demo02(int n){
if(n==1) return 1;
if(n==2) return 2;
if(n==3) return 4;
int[] f=new int[n+1];
f[0]=0;//零阶台阶
f[1]=1;//一阶台阶
f[2]=2;//两阶台阶
f[3]=4;//三阶台阶
/*i阶台阶*/
for (int i=4;i<=n;i++){
f[i]=f[i-1]+f[i-2]+f[i-3];
}
return f[n];
}
//走两步或三
public static int demo03(int n){
if(n==1) return 0;
if(n==2) return 1;
if(n==3) return 1;
int[] f=new int[n+1];
f[0]=0;//零阶台阶
f[1]=0;//一阶台阶
f[2]=1;//两阶台阶
f[3]=1;//三阶台阶
/*i阶台阶*/
for (int i=4;i<=n;i++){
f[i]=f[i-2]+f[i-3];
}
return f[n];
}
}
/**
* @author NHGA
* @creat 2020-10-23-17:00
*/
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
System.out.println(demo01(n)+" "+demo02(n)+" "+demo03(n));
}
//走一步或两
public static int demo01(int n){
if(n==1) return 1;
if(n==2) return 2;
int[] f=new int[n+1];
f[0]=0;//零阶台阶
f[1]=1;//一阶台阶
f[2]=2;//两阶台阶
/*i阶台阶*/
for (int i=3;i<=n;i++){
f[i]=f[i-1]+f[i-2];
}
return f[n];
}
//走一步或两或三
public static int demo02(int n){
if(n==1) return 1;
if(n==2) return 2;
if(n==3) return 4;
int[] f=new int[n+1];
f[0]=0;//零阶台阶
f[1]=1;//一阶台阶
f[2]=2;//两阶台阶
f[3]=4;//三阶台阶
/*i阶台阶*/
for (int i=4;i<=n;i++){
f[i]=f[i-1]+f[i-2]+f[i-3];
}
return f[n];
}
//走两步或三
public static int demo03(int n){
if(n==1) return 0;
if(n==2) return 1;
if(n==3) return 1;
int[] f=new int[n+1];
f[0]=0;//零阶台阶
f[1]=0;//一阶台阶
f[2]=1;//两阶台阶
f[3]=1;//三阶台阶
/*i阶台阶*/
for (int i=4;i<=n;i++){
f[i]=f[i-2]+f[i-3];
}
return f[n];
}
}
发表于 2020-10-23 17:44:45
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.println(help1(n)+" "+help2(n)+" "+help3(n));
}
private static int help1(int n){
if(n==1) return 1;
if(n==2) return 2;
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
for(int i = 3;i<=n;i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
private static int help2(int n){
if(n==1) return 1;
if(n==2) return 2;
if(n==3) return 4;
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
for(int i = 4;i<=n;i++){
dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
}
return dp[n];
}
private static int help3(int n){
if(n==1) return 0;
if(n==2) return 1;
if(n==3) return 1;
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 0;
dp[2] = 1;
dp[3] = 1;
for(int i = 4;i<=n;i++){
dp[i] = dp[i-2] +dp[i-3];
}
return dp[n];
}
}
发表于 2020-08-20 11:11:03
回复(0)
num = int(input()) ans_1 = [1,2,3,5] ans_2 = [1,2,4,7] ans_3 = [0,1,1,1] if num > 4: for i in range(num - 4): ans_1.append(ans_1[3 - 1 + i] + ans_1[3 - 0 + i]) ans_2.append(ans_2[3 - 2 + i] + ans_2[3 - 1 + i] + ans_2[3 - 0 + i]) ans_3.append(ans_3[3 - 2 + i] + ans_3[3 - 1 + i]) print(str(ans_1[num - 1])+' '+str(ans_2[num - 1])+' '+str(ans_3[num - 1]))
发表于 2020-03-02 18:45:12
回复(0)
问题信息
通过挑战的用户
-
2022-11-07 17:54:24 -
2022-11-04 18:25:25
-
2022-11-03 20:26:24
-
2022-11-03 16:38:13 -
2022-10-24 14:05:58
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
