思路:设f(n)表示到第n步时总共有f(n)种投骰子的方法,那么到第n-1步时总共有f(n-1)种投骰子的方法;那么到第n-2步时总共有f(n-2)种投骰子的方法...... 规律: 从第n-1步到第n步,只有一种可能性(投骰子结果为 1 ),所以从第n-1步到第n步共有f(n-1)*1 种投骰子的方法; 从第n-2步到第n步,只有一种可能性(投骰子结果为 2 ),所以从第n-2步到第n步共有f(n-2)*1 种投骰子的方法; 从第n-3步到第n步,只有一种可能性(投骰子结果为 3 ),所以从第n-3步到第n步共有f(n-3)*1 种投骰子的方法; 依次类推:f(n) = f(n-1)+f(n-2)+f(n-3)+....+f(1)+f(0),且f(1)=f(0)=1; 代码: import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner scan = new Scanner(System.in); int n = scan.nextInt(); System.out.println(getSum(n)); } public static int getSum(int n){ int count=0; if(n==1) count=1;//f(1) =1 else if(n==2) count=2;//f(2)=2 else{ for(int i=1;i<n;i++){ count+=getSum(n-i);//计算f(n) = f(n-1)+f(n-2)+f(n-3)+....+f(1) } count=count+1;//再加f(0) = 1 } return count; } }
//用dp[i]表示走到i步的种树,递推公式为dp[i] = dp[i - 1] + dp[i - 2] + ......dp[i - 6] //分别表示i-1步再走一步,i-2步再走2步...i-6步再走6步的情况。 import java.util.*; /** * Created by 梅晨 on 2017/8/20. */ public class Main { public static void main(String[] args){ Scanner in = new Scanner(System.in); while (in.hasNext()){ int num = in.nextInt(); System.out.println(dep(num)); } } public static int dep(int num){ int[] dp = new int[num + 1]; dp[0] = 1; for(int i = 1; i <= num; i++){ for(int j = 1; j <= 6; j++){ if(i >= j){ dp[i] += dp[i - j]; } } } return dp[num]; } }
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String strN; while((strN = br.readLine()) != null){ int n = Integer.parseInt(strN); System.out.println(solve(n)); } } private static int solve(int n) { if(n == 1) return 1; return 2 * solve(n - 1); // 乘以2是因为对称,可以是最后走的一步,也可以是刚开始走的一步 } }
#!_*_coding:utf-8_*_ def numer(n): sum = 0 #用于记录每次分解得到的步数 if n == 1 or n == 0: return 1 else: for i in range(n):# 根据当前n的值,循环n次,将其分解为f(0) + f(1) + ... + f(n-1) sum += numer(i) return sum # 返回当前n进行的步数
import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); final int i = sc.nextInt(); final int[] ints = new int[i]; ints[0] = 1; for (int j = 1; j < ints.length; j++) { for (int k = 0; k < j; k++) { ints[j] += ints[k]; } ints[j]++; } System.out.println(ints[i-1]); } }
#include<iostream> #include<string.h> using namespace std; int main() { string s1, s2; getline(cin, s1); getline(cin, s2); int row = s1.size(); int col = s2.size(); int dp[row][col]; memset(dp, 0, sizeof(dp)); int len = 0; for (int i = 0; i < row; i++) { dp[i][0] = s1[i] == s2[0] ? 1 : 0; len = max(len, dp[i][0]); } for (int j = 0; j < col; j++) { dp[0][j] = s1[0] == s2[j] ? 1 : 0; len = max(len, dp[0][j]); } for (int i = 1; i < row; i++) { for (int j = 1; j < col; j++) { if (s1[i] == s2[j]) { dp[i][j] = dp[i - 1][j - 1] + 1; len = max(len, dp[i][j]); } } } cout<<len; }
[编程题]大富翁游戏
[编程题]拼凑钱币
[编程题]最大矩形面积
[编程题]最长公共连续子串
这道题限制了,降低了问题难度,我首先想到的是插板法。
总共走n步,最多分n次走。这个问题就相当于把n个小球分隔为~份,也就是n-1的空隙的插板问题。插1个板就是,插2个板就是,所有情况加和就是。
当我非常得意地把代码都写出来突然感觉有点不对劲,这TM不就是的二项式展开吗?淦!
然后我又自己写了一个求2的幂的函数,实际上也可以直接用Math.pow()。
import java.util.Scanner; public class Main { public static void main(String[] args){ Main s=new Main(); int a=(new Scanner(System.in)).nextInt(); System.out.print(new Double( Math.pow(2,n-1)).intValue()); } //求2^a int t(int a){ int ans=1; while(--a>0){ ans*=2; } return ans; } //求题解 int p(int a){ int ans=0; for (int i=0;i<a;i++){ ans+=c(i,a-1); } return ans; } //求b选择a的可能性 int c(int a,int b){ return x(b)/(x(b-a)*x(a)); } //求阶乘a! int x(int a){ if (a==1||a==0) return 1; return a*x(a-1); } }