前言

??????Leetcode算法系列：https://leetcode-cn.com/study-plan/algorithms/?progress=njjhkd2

??????简单总结一下动态规划相关的算法题：

??????关于动态规划的介绍见博客：https://blog.csdn.net/Little_ant_/article/details/124231043

一、爬楼梯

??????题目链接：https://leetcode-cn.com/problems/climbing-stairs/

??????题目描述：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

DP

??????此问题的状态可以描述为，f(n) ：爬到第 n 阶可以采用的方法个数。根据题意可知：由于每次可以爬 1 个或 2 个台阶，所以想要爬到第 n 阶需要先到达 n-1 阶或先到达 n-2 阶，这两种情况都可以到达第 n 阶，在第 n-1 阶只能在爬 1 个台阶，在第 n-2 阶只能爬 2 个台阶（在此时爬 1 个台阶的情况已经包含在 f(n-1) 中了）。

??????状态转移方程为：f(n)=f(n-1)+f(n-2)，等于 f(n-1) 和 f(n-2) 的方法数之和。

??????参考算法如下：

    public int climbStairs(int n) {
        if(n==1)
            return 1;
        if(n==2)
            return 2;
        int[] ans=new int[n];
        ans[0]=1;
        ans[1]=2;
        for(int i=2;i<n;i++)
            ans[i]=ans[i-1]+ans[i-2];
        return ans[n-1];
    }

二、打家劫舍

??????题目链接：https://leetcode-cn.com/problems/house-robber/

??????题目描述：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

DP：

??????假设有 n 间屋子，在偷到 n 间屋子所能得到的最大金额取决于一个限制条件，即是否在第 n-1 间屋子偷东西。如果偷的话：那么在 n 间屋子偷到的最大金额等于在前 n-1 间屋子里偷到的最大金额；否则等于在前 n-2 间屋子中偷到的最大金额加上第 n 间屋子中的金额。

??????所以状态描述为，f(n)：一直到偷到第 n 间屋子所能得到的最大金额。

??????状态转移方程为：f(n)=max(f(n-1)，f(n-2)+第 n 间屋子的金额）。
??????参考算法如下：

    public int rob(int[] nums) {
        int len=nums.length;
        int[] dp=new int[len+1];
        dp[1]=nums[0];
        for(int i=2;i<dp.length;i++)
            dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i-1]);
        return dp[dp.length-1];
    }

三、三角形最小路径和

??????题目链接：https://leetcode-cn.com/problems/triangle/

??????题目描述：
给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

DP：

??????最初将状态描述为，f(n)：在第 n 行能够得到的最小路径和。认为在第 n 行能够得到的最小路径和与第 n-1 行得到最小路径和的位置有关，即从第 n-1 行中最小路径和的位置出发来判断第 n 行的最小路径和以及位置。然而这样做是有问题的，没有考虑到第 n 行中其他位置的元素（因为从上一行某个位置出发，那么总有在这一行中判断不了的位置）。

??????如果说，想直接得到某一行的最小路径和是将问题想的过于简单了，那么就稍微复杂一些，直接求出在每一行中的每一个位置的最小路径和，从一维扩展到二维。

??????所以将状态描述为，f(i，j)：在位置（i，j）处的最小路径和。

??????状态转移方程为：f(i，j)=min(f(i-1，j)，f(i-1，j-1)）。

??????参考算法如下：

    public int minimumTotal(List<List<Integer>> triangle) {
            int rowN=triangle.size();
            int[][] dp=new int[rowN][rowN];
            dp[0][0]=triangle.get(0).get(0);//第一行只有一个数
            for(int i=1;i<rowN;i++){
                dp[i][0]=dp[i-1][0]+triangle.get(i).get(0);//最左边那个数
                for(int j=1;j<i;j++)
                    dp[i][j]=Math.min(dp[i-1][j],dp[i-1][j-1])+triangle.get(i).get(j);
                
                dp[i][i]=dp[i-1][i-1]+triangle.get(i).get(i);//最右边那个数
            }
            int ans=Integer.MAX_VALUE;
            for(int i=0;i<rowN;i++)
                ans=Math.min(ans,dp[rowN-1][i]);
            return ans;
    }