/// <summary> /// 机器人 不停尝试 /// </summary> /// <param name="start">开始位置</param> /// <param name="aim">要到的位置</param> /// <param name="n">总的数</param> /// <param name="k">步数</param> /// <returns></returns> public int Way1(int start,int aim,int n,int k) { if(n <= 1 || start < 1 || start > n || aim < 1 || aim > n || k <= 0){ return -1; } return Proccess1(start, aim, n, k); } public int Proccess1(int cur,int aim,int n,int rest){ if (rest == 0) return cur == aim ? 1 : 0; // 剩余步骤是0，且恰好在目标位置。 // if(cur < 0 || cur == n) return -1; 不是0，就从1开始 *** if(cur == 1) return Proccess1(cur+1,aim,n,rest-1); if(cur == n) return Proccess1(cur-1,aim,n,rest-1); return Proccess1(cur+1,aim,n,rest-1) + Proccess1(cur-1,aim,n,rest-1); } /// <summary> /// 加缓存 可变参数决定维度 这里在递归时变化的是start，k /// </summary> /// <param name="start"></param> /// <param name="aim"></param> /// <param name="n"></param> /// <param name="k"></param> /// <returns></returns> public int Way2(int start,int aim,int n,int k) { if(n <= 1 || start < 1 || start > n || aim < 1 || aim > n || k <= 0){ return -1; } int[,] dp = new int[n+1,k+1]; for (int i = 0; i <= n; i++) { for(int j=0; j <= k; j++) { dp[i,j] = -1; } } return Proccess2(start, aim, n, k, dp); } // cur [1~n] // rest [0~k] public int Proccess2(int cur,int aim,int n,int rest,int[,] dp){ if (rest == 0) return cur == aim ? 1 : 0; // 剩余步骤是0，且恰好在目标位置。 // if(cur < 0 || cur == n) return -1; 不是0，就从1开始 *** // 我以为是一维数组了，还是要画图(树状图) /*(6,7)出现两次。有重复解 (6,9) (5,8) (7,8) (4,7) (6,7) (6,7) (8,7) */ if(dp[cur,rest] != -1) return dp[cur,rest]; if(cur == 1) { dp[cur,rest] = Proccess2(cur+1,aim,n,rest-1,dp); } else if(cur == n) { dp[cur,rest] = Proccess2(cur-1,aim,n,rest-1,dp); }else{ dp[cur,rest] = Proccess2(cur+1,aim,n,rest-1,dp) + Proccess2(cur-1,aim,n,rest-1,dp); } return dp[cur,rest]; } /// <summary> /// 动态规划 动作决定结果 填表 动态规划是结果不是原因 /// 返回的结果是：dp[start,rest] 必须在一条线上 /// </summary> /// <param name="start"></param> /// <param name="aim"></param> /// <param name="n"></param> /// <param name="k"></param> /// <returns></returns> public int Way3(int start,int aim,int n,int k) { if(n <= 1 || start < 1 || start > n || aim < 1 || aim > n || k <= 0){ return -1; } int[,] dp = new int[n+1,k+1]; // n = 4 rest = 2 start 1 aim = 3 // 怎么填，看暴力递归 rest == 0,aim = 3(行等于3) // cur=1(行等于1) cur+1,rest-1 左下 // cur=4(行等于4) cur-1,rest-1 左上 // cur=2,3中间位置, cur-1,rest-1 + cur+1,rest-1 /* 0 1 2 0 X X X 1 X x 1 2 X 1 x 3 1 x 2 4 X 1 x */ dp[aim,0] = 1; // int数组本身初始化就是0 Proccess3(start, aim, n, k, dp); return dp[start, k]; } // cur [1~n] // rest [0~k] public void Proccess3(int cur,int aim,int n,int rest,int[,] dp) { // if (rest == 0) return cur == aim ? 1 : 0; // 剩余步骤是0，且恰好在目标位置。 // 一列一列填 for(int col=1;col<=rest;col++) { dp[1,col] = dp[2,col-1]; // 第一行 for(int row=2;row<n;row++) // 第二行及之后 { dp[row,col] = dp[row-1,col-1] + dp[row+1,col-1]; } dp[n,col] = dp[n-1,col-1]; // 最后一行 } }
--所用币种数量
public void Test(){ // int start,int aim,int n,int k // var rt = Way3(2,4,5,6); // var rt = Change(); IList<Commodity> commodities = new List<Commodity>(){ new Commodity(3,5), new Commodity(2,6), new Commodity(4,3), new Commodity(7,19), new Commodity(3,12), new Commodity(1,4), new Commodity(7,2), }; int bag = 5; //var rt = MaxValue2(commodities,bag); var rt = GetMinCount(); var rt2 = GetMinCount(); System.Console.WriteLine($"结果是：{rt2},递归：{rt}"); System.Console.WriteLine("33"); } // coins面值 // 返回最小张数 /* 是否重复计算 coins = [1,2,5] amount = 15 是存在重复计算的 P(0,15) P(1,14) p(1,13) P(1,10) P(2,13) P(2,12) P(2,9) P(2,12) 2.返回值，怎么调用的 3.怎么填值，根据尝试函数 */ public int GetMinCount2( ) { var coins = new int[]{1,2,5}; int n = coins.Count(); int k = 15; int[,] dp = new int[n+1,k+1]; // dp[n,0] = 0; for(int j=1;j<=n;j++) { dp[n,j] = int.MaxValue; } for(int row = n-1;row>=0;row++) { for(int col=0;col<=k;col++) { int ans = int.MaxValue; // coin所需硬币数 for (int coin = 0; coin * coins[row] <= col; coin++) { int next = dp[col+1,col - col-coins[row]]; // GetMinCountProccess(coins,index+1,rest - coin*coins[index]); if(next != int.MaxValue) { ans = Math.Min(ans, next + coin); } } dp[row,col] = ans; } } return dp[0,k]; } // coins面值 // 返回最小张数 public int GetMinCount( ) { var coins = new int[]{1,2,5}; var rt = GetMinCountProccess(coins,0,15); return rt; } public int GetMinCountProccess(int[] coins,int index,int rest) { if(index == coins.Length) { return rest == 0 ? 0 : int.MaxValue; }else { int ans = int.MaxValue; // coin所需硬币数 for (int coin = 0; coin * coins[index] <= rest; coin++) { int next = GetMinCountProccess(coins,index+1,rest - coin*coins[index]); if(next != int.MaxValue) { ans = Math.Min(ans, next + coin); } } return ans; } }