public int[] countBits(int num) {
int[] result = new int[num+1];
result[0] = 0;
if (num!=0)
{
int flag = 0;
for (int i =1; i<=num;i++)
{
result[i] = result[flag]+1;
flag++;
if (flag+1>num||result[flag+1]==0)
flag=0;
else flag++;
}
}
return result;
}
没啥好说的从头到尾扫描
public int integerBreak(int n) {
if (n == 2)
return 1;
if (n == 3)
return 2;
return (int)Math.pow(3, (n-2)/3)*((n-2)%3+2);
}
这道题的名字叫做 凑3.
public int numTrees(int n) {
int[] resultSet = new int[n+1];
resultSet[0] = 1;
resultSet[1] = 1;
if (n<2)
return resultSet[n];
for (int i = 2; i <n ; i++) {
int temp = 0;
for (int j = 0; j <i ; j++) {
temp += resultSet[j]*resultSet[i-1-j];
}
resultSet[i] = temp;
}
return resultSet[n];
}
最优子结构 Σ（根节点*左子树的个数*右子树的个数）
public int DP (int l,int r,int[] nums,int[][] dp)
{
if (dp[l][r] > 0)
return dp[l][r];
for (int x = l; x <= r; x++) {
dp[l][r] = Math.max(dp[l][r], DP(l, x - 1, nums, dp) + nums[l - 1] * nums[x] * nums[r + 1] +
DP(x + 1, r, nums, dp));
}
return dp[l][r];
}
public int maxCoins(int[] nums) {
int n = nums.length;
int[] temp = new int[n + 2];
for (int i = 0; i < n; i++)
temp[i + 1] = nums[i];
temp[0] = temp[n + 1] = 1;
int[][] dp = new int[n + 2][n + 2];
return DP(1, n, temp, dp);
}
从只剩1个气球开始想 最优子结构 dp[l][r] = Math.max(dp[l][r], DP(l, x - 1, nums, dp) + nums[l - 1] * nums[x] *
nums[r + 1] + DP(x + 1, r, nums, dp));
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0)
return 0;
int len = prices.length;
int[] sell = new int[len];
int[] coolDown = new int[len];
sell[0] = 0;
coolDown[0] = 0;
for (int i = 1; i < len; i++) {
sell[i] = Integer.max(sell[i - 1] + prices[i] - prices[i - 1], coolDown[i - 1]);
coolDown[i] = Integer.max(sell[i - 1], coolDown[i - 1]);
}
return Integer.max(sell[len - 1], coolDown[len - 1]);
}
最优子结构 Max= max（sell,coolDown）,sell[i] = Integer.max(sell[i - 1] + prices[i] - prices[i - 1],
coolDown[i - 1]);
coolDown[i] = Integer.max(sell[i - 1], coolDown[i - 1]);
public int climbStairs(int n) {
if (n==0)
return 0;
if (n==1)
return 1;
if (n==2)
return 2;
int[] resultSet = new int[n+1];
resultSet[0] = 0;
resultSet[1] = 1;
resultSet[2] = 2;
for (int i =3; i<=n;i++)
{
resultSet[i] = resultSet[i-1]+resultSet[i-2];
}
return resultSet[n];
}
没啥可说的，resultSet[i] = resultSet[i-1]+resultSet[i-2];
参见Array I
public int uniquePaths(int m, int n) {
if (m==0&&n==0)
return 0;
if (m==1&&n==1)
return 1;
int[][] resultSet = new int[m][n];
for (int i = 0; i <m ; i++) {
resultSet[i][0] = 1;
}
for (int i = 0; i <n ; i++) {
resultSet[0][i] = 1;
}
for (int i = 1; i <m ; i++) {
for (int j = 1; j <n ; j++) {
resultSet[i][j] = resultSet[i-1][j] + resultSet[i][j-1];
}
}
return resultSet[m-1][n-1];
}
最优子结构 resultSet[i][j] = resultSet[i-1][j] + resultSet[i][j-1];
参见Array I
public int minPathSum(int[][] grid) {
int height = grid.length;
int width = grid[0].length;
for (int i = 0; i< height; i++)
for (int j = 0; j<width ; j ++)
{
if (i==0&&j==0) {
continue;
}
else if(i==0) {
grid[i][j] += grid[i][j-1];
}
else if(j==0) {
grid[i][j] += grid[i-1][j];
}
else {
grid[i][j] += Math.min(grid[i-1][j],grid[i][j-1]);
}
}
return grid[height-1][width-1];
}
从左到右，从上到下，选最小值叠加grid[i][j]=(grid[i][j]+Math.min(grid[i-1][j],grid[i][j-1]));
