leetCode 322. 零钱兑换

class Solution {
    // dp[i] = dp[i-1]+dp[i-2] ?????  可以使用宽搜的方式来处理最短路径问题
    // dp[i] = min(dp[n-1],dp[n-2],...,dp[1])  k in [1,2,5]
    //思路分析： 有多条路径可以走 (使用自底向上的动态规划)
    public int coinChange(int[] path, int amount) {
        int[][]dp = new int[amount+1][path.length+1];

        for(int amt=1;amt<dp.length;++amt)
        {
            for(int j=0;j<dp[0].length;++j)
            {
                //if(i==0) continue;
                dp[amt][j] = amount+1;
            }
        }



     
        for(int i=1;i<=amount;++i)
        {
            for(int j=1;j<=path.length;++j)
            {
                if(i>=path[j-1])
                {
                    dp[i][j]= Math.min( dp[i][j-1] , dp[ i-path[j-1] ][j] + 1);
                }else{
                    dp[i][j] = dp[i][j-1];
                }
            }
        }

        return dp[amount][path.length] >amount? -1:dp[amount][path.length];
    }
}

我们来看一下这个题的递归树，根据递归树写出状态转移方程

dp[i][j] = min(dp[i][j-1],dp[i-coin[j]][j]+1)
// i表示 有 i块钱
// j表示 coins[j] 对应的索引
// dp 表示这个递归树求的最短的路径

压缩一下空间

class Solution {
    // dp[i] = dp[i-1]+dp[i-2] ?????  可以使用宽搜的方式来处理最短路径问题
    // dp[i] = min(dp[n-1],dp[n-2],...,dp[1])  k in [1,2,5]
    //思路分析： 有多条路径可以走 (使用自底向上的动态规划) dp[i]=min(dp[i],dp[i-coin]+1)
    public int coinChange(int[] path, int amount) {
        int[] dp = new int[amount+1] ;

        Arrays.fill(dp,amount+1);
        dp[0] = 0;
        for(int i=1;i<dp.length;++i)
        {
            for(int j=0;j<path.length;++j)
            {
                if(i>=path[j])
                {
                    dp[i] = Math.min(dp[i],dp[i-path[j]]+1);//计算步数
                }
            }
        }
        return dp[amount]>amount?-1:dp[amount]; 

    }
}

当然，既然可以画出一颗递归树，那么就可以求这颗递归树的最短路径，这个问题就转化为了最短路径问题
使用bfs

class Solution {
    // dp[i] = dp[i-1]+dp[i-2] ?????  可以使用宽搜的方式来处理最短路径问题
    // dp[i] = min(dp[n-1],dp[n-2],...,dp[1])  k in [1,2,5]
    //思路分析： 有多条路径可以走 (使用自底向上的动态规划) dp[i]=min(dp[i],dp[i-coin]+1)
    public int coinChange(int[] path, int amount) {
        if(amount==0) return 0;

        Queue<Integer> q = new LinkedList<>();
        q.offer(amount);
        int level=0;
        boolean[] visited = new boolean[amount+1];
        visited[amount]=true;
        while(!q.isEmpty())
        {
            ++level;
            int len = q.size();
            for(int t=0;t<len;++t)
            {
                Integer node = q.poll();
                for(int p:path)
                {
                    if(node>=p)
                    {
                        int nextNode = node-p;
                        
                        if(!visited[nextNode])
                        {
                            q.offer(nextNode);
                            visited[nextNode]=true;
                            if(nextNode==0) return level;
                        }

                    }
                }
            }
        }
        return -1;
       

    }
}