七牛 笔试 做到了这样一道题

抖个机灵，编程题可以调试，用来跑第一题。。。（跟上次笔试一哥们儿学的）

前两个是排列组合，第三个是最简单的dp 预处理最左边和最上边，其他 dp[i][j]=min(dp[i-1][j],dp[i][j-1])+a[i][j];

七牛听同学说只招几个人，所以我没认真做。不过感觉题目不难，提前1个多小时就交了

public class Solution {     public int  min(int a,int b){ return ((a)<(b)?(a):(b)); }     public int minPathSum(int[][] grid) {     int i,j,m,n;       int [][] dp = new int[100][100];     n = grid.length;     m = grid[0].length;     dp[0][0]=grid[0][0];       for(i = 1;i<m;i++){     dp[0][i] = dp[0][i-1]+grid[0][i];//横      }     for(j = 1;j<n;j++){     dp[j][0] = dp[j-1][0]+grid[j][0];//纵      }          for(i=1;i<n;i++)           for(j=1;j<m;j++){  //中间部分的计算              dp[i][j] = min(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j]);           }             return dp[n-1][m-1];         } }

#include<stdio.h> #include<string.h>  #include<stdlib.h> int main(){ int i,sum = 2; char a[6]={0}; for(i = 0;i<100;i++){ if(i>10 && i<=99){ itoa(i,a,10);//覆盖方式  if(a[1]== '3' || a[1] == '4' || a[0] == '3' || a[0]=='4')//先判断个位 是3 或者是4 的话就加加  { sum++; } //printf("%s",a); memset(a, 0, sizeof(a)); } else if(i>=100 && i<=999){ itoa(i,a,10);//覆盖方式  if(a[2]== '3' || a[2] == '4'||a[1]== '3' || a[1] == '4' || a[0] == '3' || a[0]=='4')//先判断个位 是3 或者是4 的话就加加  { sum++; } memset(a, 0, sizeof(a)); } else if(i>=1000 && i<=10000){ itoa(i,a,10);//覆盖方式  if(a[3]== '3' || a[3] == '4'||a[2]== '3' || a[2] == '4'||a[1]== '3' || a[1] == '4' || a[0] == '3' || a[0]=='4')//先判断个位 是3 或者是4 的话就加加  { sum++; } memset(a, 0, sizeof(a)); } } printf("%d",sum); }

第三题是一道简单dp，都遇到很多次了！

f(n-2)种题解；2，放入除盒子n和i以外的盒子，子问题有f(n-1)种题解！综上，递推式为：f(n)=(n-1)*(f(n-1)+f(n-2))

第二题：设有n个球和n个盒子，用f(n)表示题解，则球n有n-1种放法，假设放到盒子i中，那么球i有两种可能：1，放入盒子n中，此时除去编号i和n的球和盒子，剩余子问题有f

第一题叫数位dp 其实当dfs写也行。 从低位到高位考虑：考虑这一位自己是3或4的，加上这一位不是3或4，但低几位有3或4的和。 （说实话，我还是不会写0~895246，有多少个带3或4这种，上界不是整的题…… 低位到高位操作，算没上界和有上界2种情况？） 第二题是错位排列问题，可以根据容斥原理现场推…… 但是首先高考不要求容斥原理的理解…… 第三题不会那是真挂飞了…… 第三题说是递推/动态规划，其实也可以直接套最短路的。 每个点自己的距离是左上角到这个点的最小权值和。 然后每个点有2条边：向下或向右。 图建好了，直接求起点到终点的最短路，done。 （当然面试官应该希望看到递推的，最短路估计勉强给过……）

第二个就是高中排列组合的题吧。第三个bfs