算法Day1—动态规划（剑指offer42+47）

动态规划解题思路

1. 确定状态（两个核心，最后一步，化成子问题）

   根据最后一步，往前推。然后将问题转化成从开始到最后一步的子问题。

2. 状态转移方程 结果=开始到最后一步+最后一步。

3. 开始和边界条件 确定0，以及边界不适合转移方程的条件。

4. 计算顺序 一般都是推导到从最开始计算。

剑指offer47：礼物的最大价值

题目：在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

状态转移方程：dp(i,j)=max(dp(i-1,j),dp(i,j-1))+grid(i,j)

边界：dp(0,0)=grid(0,0);

dp(0,j)=dp(0,j-1)+grid(0,j); dp(i,0)=dp(i-1,0)+grid(i,0)

class Solution{
	public int maxValue(int[][] grid){
		int m=grid.length, n=grid.length[0];
		for(int j=1; j<n; j++) grid[0][j]+=grid[0][j-1];  //for用；不是，
		for(int i=1; i<m; i++) grid[i][0]+=grid[i-1][0];
		for(int i=1; i<m; i++){
			for(int j=1; j<n; j++){
				grid[i][j]+=Math.max(grid[i-1][j],grid[i][j-1]);
			}
		}
		return grid[m-1][n-1];
	}
}

剑指offer42：连续子数组的最大和

题目：输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。

状态方程：dp[i]=max(dp[i-1]+nums[i], nums[i])

边界：dp[0]=0

class Solution{
	public int maxSetArray(int[] nums){
		int res=nums[0], n=nums.length;
		for(int i=1; i<n; i++){
			nums[i] += Math.max(nums[i-1], 0);
			res = Math.max(res, nums[1]);
		}
		return res;
	}
}

JAVA常识

之前一直用python，小细节得慢慢改qaq

1.数组

声明数组：数据类型[] 数组名称（二维[][]）

int[][] grid

 初始化：数据类型 [] 数组名称 = new 数据类型 [长度]

//动态初始化
int[] cat = new int[5];
arr[0] = 0;
arr[1] = 1;
arr[2] = 3;
arr[3] = 4;
arr[4] = 5;
//静态初始化
int[] arr2 = new int []{1,2,3,4,5};

 2. 数组长度length

一维数组，a.length 方法，返回这个数组的长度。

二维数组中，b.length方法，返回b数组的行数；b[0].length方法，返回0行所代表的长度。

3. 函数定义

修饰符 返回值类型 函数名称（参数类型 参数1，参数类型参数2， . . . ）{
        函数执行代码；
        return 返回值；
}

4. for循环

for (循环变量赋初值; 循环条件; 循环变量增值) //分号！不是逗号 {

        语句;

}