赞
踩
class Solution { public int fib(int n) { //1.确定dp数组,及下标含义:第i个斐波那契数 //2.确定递推公式,即状态转移方程:题中给出 //3.确定如何初始化dp数组,题中给出 //4.确定遍历顺序,题中给出 //5.推导验证dp数组 if(n<=1) return n; int[] dp = new int [n+1]; dp[0] = 0; dp[1] = 1; for (int i = 2; i <=n ; i++) { dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; } }
class Solution { public int climbStairs(int n) { //dp数组,爬第i层楼梯有几种方式 //dp[i] = dp[i-1]+dp[i-2] //dp[1]=1,dp[2]=2 if(n<=2) return n; int[] dp = new int [n+1]; dp[1] = 1; dp[2] = 2; for (int i = 3; i <=n ; i++) { dp[i] = dp[i-1]+dp[i-2]; } return dp[n]; } }
class Solution { public int minCostClimbingStairs(int[] cost) { //你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯 //这句话表示爬到0或1是不用支付费用的,但是从0或1开始爬是要花费的 //dp数组表示爬到第i个台阶需要支付的最小费用 //dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]) //dp[0]=0,dp[1]=0 int[] dp = new int[cost.length+1]; for (int i = 0; i <= cost.length; i++) { if(i==0||i==1) dp[i] = 0; else { dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]); } } return dp[cost.length]; } }
class Solution { public int uniquePaths(int m, int n) { //dp表示的是到达第i行j列总共有多少路径 //dp[i][j] = dp[i-1][j]+dp[i][j-1] //关键的是第一行和第一列的所有位置都只有一种方法 int[][] dp = new int[m][n]; for(int i=0;i<m;i++){ dp[i][0] = 1; } for (int i = 0; i < n; i++) { dp[0][i] = 1; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = dp[i-1][j]+dp[i][j-1]; } } return dp[m-1][n-1]; } }
class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { //有障碍物的地方dp应该直接赋值为0 //第一行和第1列只要遇到障碍物就停止赋值 int m = obstacleGrid.length; int n = obstacleGrid[0].length; int[][] dp = new int[m][n]; for (int i = 0; i < m; i++) { if(obstacleGrid[i][0] == 1) break; dp[i][0] = 1; } for (int i = 0; i < n; i++) { if(obstacleGrid[0][i] == 1) break; dp[0][i] = 1; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if(obstacleGrid[i][j] == 1){ dp[i][j] = 0; }else{ dp[i][j] = dp[i-1][j]+dp[i][j-1]; } } } return dp[m-1][n-1]; } }
class Solution { public int numTrees(int n) { //dp表示节点值从1到n组成的不同的BST数,rp表示由n个节点组成,且根节点为i的BST数 //从每个节点组成的树的角度,dp[i]=rp[1]+rp[2]+...+rp[i-1]+rp[i] //从树的左右子树角度,rp[i]=dp[i-1]*dp[n-i] //所以dp[i]=dp[1-1]*dp[n-1]+...+dp[i-1]*dp[i-i] //初始化dp[1]=dp[0]*dp[0],dp[0]=1 int[] dp = new int[n+1]; dp[0] = 1; for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++){ dp[i] += dp[j-1]*dp[i-j]; } } return dp[n]; } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。