[数据结构与算法]动态规划之硬币问题/迷宫问题

?其实动态规划对于我最难的是边界问题

动态规划四部曲：

1.确定状态，确定从什么时候开始，就是amout

2.确定转移方程，也就是?if (coins[j] <= i) {
? ? ? ? ? ? ? ? ? ? dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);//变成子问题，问题规模缩小
? ? ? ? ? ? ? ? }

3.确定初始条件和边界条件，也就是前面和后面几步

4.确定步数和尝试次数，也就是i和j的范围

class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;//设置max填充dp数列，为之后的边界问题做铺垫
        int[] dp = new int[amount + 1];//定义dp长度，因为dp是从1开始，所以需要多一格
      
        Arrays.fill(dp, max);//填充数列
       
        dp[0] = 0;//dp[0]设置值，为特殊情况做准备
      
        for (int i = 1; i <= amount; i++) {//一步步递进
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);//变成子问题，问题规模缩小
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];//判断是否正好组成总金额
    }
}

迷宫问题，即有多少条路径也有异曲同工之妙，类似与斐波那契数列

class Solution {
    public int uniquePaths(int m, int n) {
        int dp[][]=new int[m][n];
        for(int i=0;i<n;i++){
            //先设置零行的路径方法都为1
            dp[0][i]=1;
        }
        for(int i=0;i<m;i++){
            //零列的路径方法也都为1，如此设置是防止后面的数组溢出，也就是设置边界条件
            dp[i][0]=1;
        }
        if(m==0&&n==0){
            return 0;
        }
        for (int i=1;i<m;i++){//设置i和j的边界

            for (int j = 1; j <n ; j++) {

                dp[i][j]=dp[i-1][j]+dp[i][j-1];//核心方程式，与斐波那契数列相似
            }
        }
        return dp[m-1][n-1];


    }
}