/// <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;
}
}
标签：Commodity,暴力,递归,int,aim,start,var,new,动态 From： https://www.cnblogs.com/Insist-Y/p/17344166.html