题目

题目来源：Link

分析

代码

package com.graph; import java.util.*; public class Solution{ List<Integer> factorial = new ArrayList<Integer>(); public int solve(int n){ if (n==0) {//易遗漏 return 1; } if(n>10) n=11; n++;//转成实际位数 factorial.add(1); //n<=10 int[] nums = new int[n+1]; int t=1; int res=0; for(; t<n; t++){ if(t==1) {//易遗漏 nums[t] = 10; }else { //对于首位，为1~9种选择 //剩下t-1位，为9种选择 nums[t] = 9*(getFactorial(9)/getFactorial(9-(t-1)));//之前考虑遗漏被除数 } res = res+nums[t]; } System.out.println(res); return res; } int getFactorial(int fac){ int size = factorial.size(); if(fac<=size){ return factorial.get(fac-1); } for(int i=size+1; i<=fac; i++){ int topIndex = factorial.size()-1; int tmp = factorial.get(topIndex)*i; factorial.add(tmp); } return factorial.get(factorial.size()-1); } //优化方法，参考原始题目代码 //动态规划 public int solve_dp(int n) { //不能理解题给的公式 return 0; } //排列组合 public int solve_pe(int n) { if(n==0) return 1; if(n>10) n=10; int ans = 1; int mul = 9; for(int i=n-1; i>=0; i--) { if(i==0) { ans+=mul; }else { ans+=(n-i+1)*mul; } mul = mul*(10-n+i-1); } return ans; } public static void main(String[] args) { Solution s = new Solution(); s.solve(2); //s.solve(new int[] {1,2,4,8,7,9,6,3}); } }